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

题意

直接遍历即可

思路

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

时间复杂度：$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

题意

前缀和

思路

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

时间复杂度：$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

题意

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

思路

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

二分查找：我们知道无论如何摆放，最终最多的覆盖一定是从某个连续区间内的起点或者终点开始摆放，我们依次枚举每个起点 $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]$ 所能覆盖的瓷砖数即可，我们采用动态线树即可解决这个问题，同样类似的题目还有许多方法可以解决。

复杂度分析：

时间复杂度：$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

题意

动态规划

思路

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

时间复杂度：$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
关注我的微信公众号: 公务程序猿

力扣周赛

#力扣周赛

leetcode biweekly contest 78

http://example.com/2022/01/01/力扣周赛题解/2/

Author

Mike Meng

Posted on

January 1, 2022

Updated on

September 8, 2026

Licensed under

leetcode contest biweekly 81 Previous

leetcode contest 295 Next