Leetcode 第 78 场双周赛题解

1. 找到一个数字的 K 美丽值

简单题，注意判断子字符串对应的数字不能为 0 即可。

class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string s = to_string(num);
        int ans = 0;
        for (int i = 0; i + k - 1 < s.size(); ++i) {
            int x = stoi(s.substr(i, k));
            if (x != 0 && num % x == 0) {
                ++ans;
            }
        }
        return ans;
    }
};

2. 分割数组的方案数

简单的前缀和，复杂度 $O(n)$。

class Solution {
    using ll = long long;

public:
    int waysToSplitArray(vector<int> &nums) {
        int n = nums.size();

        auto sum = vector<ll>(n + 1);

        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            if (sum[i] >= sum[n] - sum[i]) ++ans;
        }
        return ans;
    }
};

3. 毯子覆盖的最多白色砖块数

因为毯子不重叠，排序后直接双指针贪心。从前往后贪心，每次贪心确保加上第 $i$ 块地毯后，覆盖瓷砖数是最多的。因为加入第 $i$ 块地毯后，可能毯子长度不够，每次往前移动最小的毯子数即可。时间复杂度 $O(nlogn)$。

class Solution {
    int length(vector<int> &tile) {
        return tile[1] - tile[0] + 1;
    }
public:
    int maximumWhiteTiles(vector<vector<int>> &tiles, int carpetLen) {
        sort(tiles.begin(), tiles.end());

        int n = tiles.size();
        int left = 0;
        int count = 0;
        int ans = 0;

        for (int i = 0; i < n; ++i) {
            count += length(tiles[i]);

            int len = tiles[i][1] - tiles[left][0] + 1;
            while (left < i && len > carpetLen) {
                int advance = min(len - carpetLen, length(tiles[left]));

                count -= advance;
                len -= advance;
                tiles[left][0] += advance;

                if (tiles[left][0] > tiles[left][1]) {
                    ++left;
                    len = tiles[i][1] - tiles[left][0] + 1;
                }
            }
            ans = max(ans, count);
        }

        return ans;
    }
};

假设最多的字符为 $x$，最少的字符为 $y$。那么字符串 $s$ 中，$s[i]=x$ 对答案贡献为 $1$，$s[i]=y$ 对答案贡献为 $-1$，其他字符对答案无贡献。那么相当于找一个贡献最大的连续子序列。需要注意的是 $x$ 和 $y$ 都存在的时候才可以对答案做贡献。可以通过 dp 或 贪心 解决。最后枚举 $x$, $y$ 的所有可能即可。时间复杂度 $O(26 \times 26 n)$。

const int N = 1e4 + 5;
const int INF = 0x3f3f3f3f;
int dp[N][2];

class Solution {
public:
    int largestVariance(string s) {
        int n = s.length();
        int ans = 0;

        for (char x = 'a'; x <= 'z'; ++x) {
            for (char y = 'a'; y <= 'z'; ++y) {
                if (x == y) continue;

                dp[0][0] = 0;
                dp[0][1] = -INF;

                for (int i = 1; i <= n; ++i) {
                    if (s[i - 1] == x) {
                        dp[i][0] = dp[i - 1][0] + 1;
                        dp[i][1] = dp[i - 1][1] + 1;
                    } else if (s[i - 1] == y) {
                        dp[i][0] = 0;
                        dp[i][1] = max({0, dp[i - 1][1], dp[i - 1][0]}) - 1;
                    } else {
                        dp[i][0] = dp[i - 1][0];
                        dp[i][1] = dp[i - 1][1];
                    }
                    ans = max(ans, dp[i][1]);
                }
            }
        }
        return ans;
    }
};

上面的 $dp[i][0]$ 代表不包含字符 $y$ 时, 以 $i$ 结尾后缀中, 字符 $x$ 的 最大贡献，$dp[i][1]$ 包含字符 $y$ 时, 以 $i$ 结尾后缀中, 字符 $x$ 和字符 $y$ 的 最大贡献。那么 $\max_i dp[i][1]$ 就是子字符串的 最大波动。