leetcode biweekly contest 78

双周赛的题目质量明显好于周赛。

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

题目

一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：

• 子字符串长度为 k 。
• 子字符串能整除 num 。
• 给你整数 num 和 k ，请你返回 num 的 k 美丽值。

注意：

• 允许有 前缀 0 。
• 0 不能整除任何值。
• 一个 子字符串 是一个字符串里的连续一段字符序列。

示例 1：

输入：num = 240, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "240" 中的 "24" ：24 能整除 240 。
- "240" 中的 "40" ：40 能整除 240 。
所以，k 美丽值为 2 。

示例 2：

输入：num = 430043, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "430043" 中的 "43" ：43 能整除 430043 。
- "430043" 中的 "30" ：30 不能整除 430043 。
- "430043" 中的 "00" ：0 不能整除 430043 。
- "430043" 中的 "04" ：4 不能整除 430043 。
- "430043" 中的 "43" ：43 能整除 430043 。
所以，k 美丽值为 2 。

提示：

• 1 <= num <= 109
• 1 <= k <= num.length （将 num 视为字符串）

地址

https://leetcode.cn/problems/find-the-k-beauty-of-a-number

题意

直接遍历即可

思路

1. 直接统计即可。
2. 复杂度分析：

• 时间复杂度：$O(\log^2 n)$, 其中 $n$ 为数字。
• 空间复杂度：$O(\log n)$。

代码

class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string s = to_string(num);
        int ans = 0;
        int curr = 0;
        for (int i = 0; i <= s.size() - k; i++) {
            int curr = 0;
            for(int j = i; j < i + k; j++) {
                curr = curr * 10 + s[j] - '0';
            }
            if (curr > 0 && (num % curr) == 0) {
                ans++;
            }
        }
        return ans;
    }
};

2270. 分割数组的方案数

题目

给你一个下标从 0 开始长度为 n 的整数数组 nums 。
如果以下描述为真，那么 nums 在下标 i 处有一个 合法的分割 ：

• 前 i + 1 个元素的和 大于等于 剩下的 n - i - 1 个元素的和。
• 下标 i 的右边 至少有一个 元素，也就是说下标 i 满足 0 <= i < n - 1 。
  请你返回 nums 中的 合法分割 方案数。

示例 1：

输入：nums = [10,4,-8,7]
输出：2
解释：
总共有 3 种不同的方案可以将 nums 分割成两个非空的部分：
- 在下标 0 处分割 nums 。那么第一部分为 [10] ，和为 10 。第二部分为 [4,-8,7] ，和为 3 。因为 10 >= 3 ，所以 i = 0 是一个合法的分割。
- 在下标 1 处分割 nums 。那么第一部分为 [10,4] ，和为 14 。第二部分为 [-8,7] ，和为 -1 。因为 14 >= -1 ，所以 i = 1 是一个合法的分割。
- 在下标 2 处分割 nums 。那么第一部分为 [10,4,-8] ，和为 6 。第二部分为 [7] ，和为 7 。因为 6 < 7 ，所以 i = 2 不是一个合法的分割。
所以 nums 中总共合法分割方案受为 2 。

例 2：

输入：nums = [2,3,1,0]
输出：2
解释：
总共有 2 种 nums 的合法分割：
- 在下标 1 处分割 nums 。那么第一部分为 [2,3] ，和为 5 。第二部分为 [1,0] ，和为 1 。因为 5 >= 1 ，所以 i = 1 是一个合法的分割。
- 在下标 2 处分割 nums 。那么第一部分为 [2,3,1] ，和为 6 。第二部分为 [0] ，和为 0 。因为 6 >= 0 ，所以 i = 2 是一个合法的分割。

提示：

• 2 <= nums.length <= 105
• -105 <= nums[i] <= 105

地址

https://leetcode.cn/problems/number-of-ways-to-split-array

题意

前缀和

思路

1. 存储前缀和，并按照题目要求方式进行分割即可，对 $j$ 满足 $sum[j] \ge sum[n-1]$ 即可。
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 为数组中的长度。
• 空间复杂度：$O(n)$, 其中 $n$ 为数组的长度。

代码

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        int n = nums.size();
        long long total = 0;
        int ans = 0;
        vector<long long> sum(n+1);
        for (int i = 0; i < n; i++) {
            sum[i+1] = sum[i] + nums[i];
        }
        for (int i = 0; i < n - 1; i++) {
            long long left = sum[i + 1];
            long long right = sum[n] - left;
            if (left >= right) {
                ans++;
            }
        }
        return ans;
    }
};

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

题目

给你一个二维整数数组 tiles ，其中 tiles[i] = [li, ri] ，表示所有在 li <= j <= ri 之间的每个瓷砖位置 j 都被涂成了白色。

同时给你一个整数 carpetLen ，表示可以放在 任何位置 的一块毯子。

请你返回使用这块毯子，最多 可以盖住多少块瓷砖。

示例 1：

输入：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
输出：9
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖，所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出，瓷砖无法覆盖超过 9 块瓷砖。

示例 2：

输入：tiles = [[10,11],[1,1]], carpetLen = 2
输出：2
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 2 块瓷砖，所以我们返回 2 。

提示：

• 1 <= tiles.length <= 5 * 104
• tiles[i].length == 2
• 1 <= li <= ri <= 109
• 1 <= carpetLen <= 109
• tiles 互相 不会重叠 。

地址

https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet

题意

滑动窗口 + 二分查找 + 线段树

思路

1. 这种类型的题目可以作为典型的带边类题目，非常好的启发思想，可以有多种解法。

• 二分查找：我们知道无论如何摆放，最终最多的覆盖一定是从某个连续区间内的起点或者终点开始摆放，我们依次枚举每个起点 $l_i$，然后利用前缀和与二分查找找到 $[l_i, l_i + carpetLen)$ 这个区间所能覆盖的最多的瓷砖数。
  • 此时假设 $j$ 个区间的左起点大于等于 $l_i + carpetLen$，则此时可以知道当前覆盖的瓷砖的数目为：
    $$
    sum[j-1] - sum[i] + \min(tiles[i][0] + carpetLen, tiles[j-1][1] + 1) - tiles[j-1][0]
    $$
  • 根据以上递推公式即可。
• 滑动窗口: 我们每次枚举窗口的左端点，每次移动窗口即可。可以参考题解的[贪心证明，写的非常详细。
• 线段树: 可以用典型的线段树查找 $[l_i,l_i + carpetLen - 1]$ 所能覆盖的瓷砖数即可，我们采用动态线树即可解决这个问题，同样类似的题目还有许多方法可以解决。

2. 复杂度分析：

• 时间复杂度：$O(n \log n)$, 其中 $n$ 为数组的长度。
• 空间复杂度：$O(1)$。

代码

• 二分查找

  class Solution { public: int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) { int n = tiles.size(); sort(tiles.begin(), tiles.end()); vector<int> sum(n + 1); int ans = 0; for (int i = 0; i < n; i++) { sum[i + 1] = sum[i] + tiles[i][1] -tiles[i][0] + 1; } for (int i = 0; i < n; i++) { vector<int> target = {tiles[i][0] + carpetLen, 0}; int j = lower_bound(tiles.begin(), tiles.end(), target) - tiles.begin(); ans = max(ans, sum[j-1] - sum[i] + min(tiles[i][0] + carpetLen, tiles[j-1][1] + 1) - tiles[j-1][0]); } return ans; } };

• 滑动窗口

  class Solution { public: int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) { sort(tiles.begin(), tiles.end()); long long now = 0, ans = 0; for (int i = 0, j = 0; i < tiles.size(); i++) { while (j < tiles.size() && tiles[j][1] + 1 - tiles[i][0] <= carpetLen) { now += tiles[j][1] - tiles[j][0] + 1; j++; } if (j < tiles.size()) { ans = max(ans, now + max(0, tiles[i][0] + carpetLen - tiles[j][0])); } else { ans = max(ans, now); } now -= tiles[i][1] - tiles[i][0] + 1; } return ans; } };

• 线段树

  class Solution { public: void update(int start, int end, int l, int r, int idx) { if (start > r || end < l) { return; } if (cnt[idx] == r - l + 1) { return; } if (start <= l && r <= end) { cnt[idx] = r - l + 1; } else { int mid = (l + r) >> 1; if (end <= mid) { update(start, end, l, mid, idx * 2); } else if (start > mid) { update(start, end, mid + 1, r, idx * 2 + 1); } else { update(start, mid, l, mid, idx * 2); update(mid + 1, end, mid + 1, r, idx * 2 + 1); } cnt[idx] = cnt[idx * 2] + cnt[idx * 2 + 1]; } } int query(int start, int end, int l, int r, int idx) { if (start > r || end < l) { return 0; } if (start <= l && r <= end) { return cnt[idx]; } else { int mid = (l + r) >> 1; if (end <= mid) { return query(start, end, l, mid, idx * 2); } else if (start > mid) { return query(start, end, mid + 1, r, idx * 2 + 1); } else { return query(start, mid, l, mid, idx * 2) + \ query(mid + 1, end, mid + 1, r, idx * 2 + 1); } } } int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) { int ans = 0; int n = tiles.size(); for (int i = 0; i < n; i++) { update(tiles[i][0], tiles[i][1], 1, 1e9, 1); } for (int i = 0; i < n; i++) { ans = max(ans, query(tiles[i][0], min(1000000000, tiles[i][0] + carpetLen - 1), 1, 1e9, 1)); } return ans; } private: unordered_map<int, int> cnt; };

2272. 最大波动的子字符串

题目

字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。

给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。

子字符串 是一个字符串的一段连续字符序列。

示例 1：

输入：s = "aababbb"
输出：3
解释：
所有可能的波动值和它们对应的子字符串如以下所示：
- 波动值为 0 的子字符串："a" ，"aa" ，"ab" ，"abab" ，"aababb" ，"ba" ，"b" ，"bb" 和 "bbb" 。
- 波动值为 1 的子字符串："aab" ，"aba" ，"abb" ，"aabab" ，"ababb" ，"aababbb" 和 "bab" 。
- 波动值为 2 的子字符串："aaba" ，"ababbb" ，"abbb" 和 "babb" 。
- 波动值为 3 的子字符串 "babbb" 。
所以，最大可能波动值为 3 。

示例 2：

输入：s = "abcde"
输出：0
解释：
s 中没有字母出现超过 1 次，所以 s 中每个子字符串的波动值都是 0 。

提示：

• 1 <= s.length <= 104
• s  只包含小写英文字母。

地址

https://leetcode.cn/problems/substring-with-largest-variance

题意

动态规划

思路

1. 这个题目出的还算比较有意思，有点 tricky 的地方不太好做。还是好好参考题解。
2. 复杂度分析：

• 时间复杂度：$O(n)$, 其中 $n$ 为字符串的长度。
• 空间复杂度：$O(1)$。

代码

• 动态规划

  class Solution { public: int largestVariance(string &s) { int ans = 0; for (char a = 'a'; a <= 'z'; ++a) for (char b = 'a'; b <= 'z'; ++b) { if (a == b) continue; int diff = 0, diff_with_b = INT_MIN; for (char ch : s) { if (ch == a) { ++diff; ++diff_with_b; } else if (ch == b) { diff_with_b = --diff; diff = max(diff, 0); } ans = max(ans, diff_with_b); } } return ans; } };

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿