当前位置：首页 > article >正文

leetcode解题思路分析（一百六十三）1409 - 1415 题

article 2025/2/4 8:41:21

查询带键的排列
给定一个正整数数组 queries ，其取值范围在 1 到 m 之间。请你根据以下规则按顺序处理所有 queries[i]（从 i=0 到 i=queries.length-1）：
首先，你有一个排列 P=[1,2,3,…,m]。
对于当前的 i ，找到 queries[i] 在排列 P 中的位置（从 0 开始索引），然后将它移到排列 P 的开头（即下标为 0 处）。注意， queries[i] 的查询结果是 queries[i] 在 P 中移动前的位置。
返回一个数组，包含从给定 queries 中查询到的结果。

按规则匹配替换即可。

class Solution {
public:
    using EntityChar = pair <string, char>;

    vector <EntityChar> entityList;

    string entityParser(string text) {
        entityList = vector({
            (EntityChar){"&quot;", '"'},
            (EntityChar){"&apos;", '\''},
            (EntityChar){"&amp;", '&'},
            (EntityChar){"&gt;", '>'},
            (EntityChar){"&lt;", '<'},
            (EntityChar){"&frasl;", '/'}
        });

        string r = "";
        for (int pos = 0; pos < text.size(); ) {
            bool isEntity = false;
            if (text[pos] == '&') {
                for (const auto &[e, c]: entityList) {
                    if (text.substr(pos, e.size()) == e) {
                        r.push_back(c);
                        pos += e.size();
                        isEntity = true;
                        break;
                    }
                }
            }
            if (!isEntity) {
                r.push_back(text[pos++]);
                continue;
            }
        }
        return r;
    }
};

给 N x 3 网格图涂色的方案数
你有一个 n x 3 的网格图 grid ，你需要用红，黄，绿三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。给你网格图的行数 n 。请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。

规律推导：每一行只可能是ABC或者ABA这两种形式，因此，我们可以推导递推公式，最后根据公式解题。

class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int numOfWays(int n) {
        int fi0 = 6, fi1 = 6;
        for (int i = 2; i <= n; ++i) {
            int new_fi0 = (2LL * fi0 + 2LL * fi1) % mod;
            int new_fi1 = (2LL * fi0 + 3LL * fi1) % mod;
            fi0 = new_fi0;
            fi1 = new_fi1;
        }
        return (fi0 + fi1) % mod;
    }
};

逐步求和得到正数的最小值
给你一个整数数组 nums 。你可以选定任意的正数 startValue 作为初始值。你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。请你在确保累加和始终大于等于 1 的前提下，选出一个最小的正数作为 startValue 。

题目读起来很拗口，实际就是求前缀和，如果有小于0的情况出现，则加一个Offset，否则返回1.

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int min_prefix = INT_MAX;
        int prefix = 0;
        for (auto n : nums) {
            prefix += n;
            if (prefix < 0)
                min_prefix = std::min(prefix, min_prefix);
        }
        return min_prefix < 0? 1 - min_prefix : 1;
    }
};

和为 K 的最少斐波那契数字数目
给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 ，其中 n > 2 。
数据保证对于给定的 k ，一定能找到可行解。

贪心算法解题。先把小于等于k的数全列出来，然后从大到小减。

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        vector<int> f;
        f.emplace_back(1);
        int a = 1, b = 1;
        while (a + b <= k) {
            int c = a + b;
            f.emplace_back(c);
            a = b;
            b = c;
        }
        int ans = 0;
        for (int i = f.size() - 1; i >= 0 && k > 0; i--) {
            int num = f[i];
            if (k >= num) {
                k -= num;
                ans++;
            }
        }
        return ans;
    }
};

长度为 n 的开心字符串中字典序第 k 小的字符串
一个「开心字符串」定义为：
仅包含小写字母 [‘a’, ‘b’, ‘c’].
对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。
比方说，字符串 “abc”，“ac”，“b” 和 “abcbabcbcb” 都是开心字符串，但是 “aa”，“baa” 和 “ababbc” 都不是开心字符串。
给你两个整数 n 和 k ，你需要将长度为 n 的所有开心字符串按字典序排序。
请你返回排序后的第 k 个开心字符串，如果长度为 n 的开心字符串少于 k 个，那么请你返回空字符串。

因为只用返回第k个，所以计算每个字母开头代表的全排列数，就可以一步一步找到目标点。

class Solution {
public:
    char abc[3] = {'a', 'b', 'c'};
    char ch[3][2] = {{'b', 'c'}, {'a', 'c'}, {'a', 'b'}};
    int state[3][2] = {{1, 2}, {0, 2}, {0, 1}};
    string getHappyString(int n, int k) {
        if (k > (int)pow(2, n - 1) * 3) return "";
        string ans;
        k--;
        int p = k / (int)pow(2, n - 1);
        k %= (int)pow(2, n - 1);
        ans.push_back(abc[p]);
        for (int i = n - 1; i > 0; --i) {
            int tmp = (int)pow(2, i - 1);
            ans.push_back(ch[p][k / tmp]);
            p = state[p][k / tmp];
            k %= tmp;
        }
        return ans;
    }
};

恢复数组
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。由于数组方案数可能会很大，请你返回它对 10^9 + 7 取余后的结果。

递推暴力求解

using LL = long long;

class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int numberOfArrays(string s, int k) {
        int n = s.size();
        // 为了便于代码编写，我们使用 64 位整数类型
        LL kll = k;
        vector<int> f(n + 1, 0);
        // 递推的边界条件
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            LL num = 0, base = 1;
            // 倒序枚举 j，最多只需要枚举 10 个
            for (int j = i - 1; j >= 0 && i - j <= 10; --j) {
                // 在高位添加当前的数字，得到第 j+1 到 i 个数字组成的数
                // 注意 s 的下标是从 0 开始的
                num += (s[j] - '0') * base;
                if (num > kll) {
                    break;
                }
                // 判断是否有前导 0
                if (s[j] != '0') {
                    f[i] += f[j];
                    f[i] %= mod;
                }
                base *= 10;
            }
        }
        return f[n];
    }
};

重新格式化字符串
给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母.请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。请你返回重新格式化后的字符串；如果无法按要求重新格式化，则返回一个空字符串。

先遍历一遍取数字和字母的个数，相减绝对值小于等于一才能满足题意。然后将多的插在偶数位，少的插在奇数位即可。

class Solution {
public:
    string reformat(string s) {
        int sum_digit = 0;
        for (auto& c : s) {
            if (isdigit(c)) {
                sum_digit++;
            }
        }
        int sum_alpha = s.size() - sum_digit;
        if (abs(sum_digit - sum_alpha) > 1) {
            return "";
        }
        bool flag = sum_digit > sum_alpha;
        for (int i = 0, j = 1; i < s.size(); i += 2) {
            if (isdigit(s[i]) != flag) {
                while (isdigit(s[j]) != flag) {
                    j += 2;
                }
                swap(s[i], s[j]);
            }
        }
        return s;
    }
};