leetcode biweekly contest 85

双周赛的质量又好起来了，前几周的题目质量水平下降严重，本周开始质量好很多了。

6156. 得到 K 个黑块的最少涂色次数

题目

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第i块的颜色。字符'W'和'B'分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

示例 1：

输入：blocks = "WBBWWBBWBW", k = 7
输出：3
解释：
一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

示例 2：

输入：blocks = "WBWBBBW", k = 2
输出：0
解释：
不需要任何操作，因为已经有 2 个连续的黑块。
所以我们返回 0 。


提示：

n == blocks.length
1 <= n <= 100
blocks[i] 要么是 'W' ，要么是 'B' 。
1 <= k <= n

提示：

• n == blocks.length
• 1 <= n <= 100
• blocks[i] 要么是 'W' ，要么是 'B' 。
• 1 <= k <= n

地址

https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks

题意

滑动窗口

思路

1. 直接采用滑动窗口找到 $k$ 个长度 中黑色方块 ，找到连续的 $k$ 个长度中白色块最少的即可。
2. 复杂度分析：

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

代码

• 滑动窗口

  class Solution { public: int minimumRecolors(string blocks, int k) { int n = blocks.size(); int ans = n; int whiteCnt = 0, blackCnt = 0; for (int i = 0; i < n; i++) { if (blocks[i] == 'W') { whiteCnt++; } if (i >= k - 1) { ans = min(ans, whiteCnt); if (blocks[i - k + 1] == 'W') { whiteCnt--; } } } return ans; } };

6157. 二进制字符串重新安排顺序需要的时间

题目

给你一个二进制字符串 s 。在一秒之中，所有 子字符串 "01" 同时 被替换成 "10" 。这个过程持续进行到没有 "01" 存在。

请你返回完成这个过程所需要的秒数。

示例 1：

输入：s = "0110101"
输出：4
解释：
一秒后，s 变成 "1011010" 。
再过 1 秒后，s 变成 "1101100" 。
第三秒过后，s 变成 "1110100" 。
第四秒后，s 变成 "1111000" 。
此时没有 "01" 存在，整个过程花费 4 秒。
所以我们返回 4 。

示例 2：

输入：s = "11100"
输出：0
解释：
s 中没有 "01" 存在，整个过程花费 0 秒。
所以我们返回 0 。

提示：

• 1 <= s.length <= 1000
• s[i] 要么是'0'，要么是 '1' 。

地址

https://leetcode.cn/problems/time-needed-to-rearrange-a-binary-string

题意

直接模拟或者思维

思路

1. 直接模拟就非常简单，我们可以观察到直接模拟的时间复杂度不超过 $n^2$，因此我们可以直接模拟即可，知道字符串中没有字符串 01 出现即可。
2. 动态规划，本质上讲右侧的 $1$ 往左侧移动，如果 $1$ 前面有连续的 $0$ ,则可以讲其一直向左移动直到左侧为 $1$ 为止，此时需要等待。
3. 复杂度分析：

• 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示节点的数目。
• 空间复杂度：$O(n)$，$n$ 表示节点的数目。

代码

• 直接模拟：

class Solution {
public:
    int secondsToRemoveOccurrences(string s) {
        int n = s.size();
        int ans = 0;
        while(true) {
            bool valid = false;
            int pos = 0;
            while(pos < n - 1) {
                if(s[pos] == '0' && s[pos + 1] == '1') {
                    s[pos] = '1';
                    s[pos + 1] = '0';
                    pos += 2;
                    valid = true;
                } else {
                    pos++;
                }
            }
            if(valid){
                ans++;
            } else{
                break;
            }
        }
        return ans;
    }
};

• 动态规划：

  class Solution { public: int secondsToRemoveOccurrences(string s) { int n = s.size(); int ans = 0, cnt = 0; for (int i = 0; i < n; i++) { if(s[i] == '0') { ++cnt; } else { if (cnt > 0) { ans = max(ans + 1, cnt); } } } return ans; } };

6158. 字母移位 II

题目

给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [starti, endi, directioni] 。对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。

将一个字符 向后 移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 'z' 变成 'a'）。类似的，将一个字符 向前 移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 'a' 变成 'z' ）。

请你返回对 s 进行所有移位操作以后得到的最终字符串。

示例 1：

输入：s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
输出："ace"
解释：首先，将下标从 0 到 1 的字母向前移位，得到 s = "zac" 。
然后，将下标从 1 到 2 的字母向后移位，得到 s = "zbd" 。
最后，将下标从 0 到 2 的字符向后移位，得到 s = "ace" 。

示例 2:

输入：s = "dztz", shifts = [[0,0,0],[1,1,1]]
输出："catz"
解释：首先，将下标从 0 到 0 的字母向前移位，得到 s = "cztz" 。
最后，将下标从 1 到 1 的字符向后移位，得到 s = "catz" 。

提示：

• 1 <= s.length, shifts.length <= 5 * 104
• shifts[i].length == 3
• 0 <= starti <= endi < s.length
• 0 <= directioni <= 1
• s 只包含小写英文字母。

地址

https://leetcode.cn/contest/biweekly-contest-85/problems/shifting-letters-ii/

题意

差分数组或者线段树

思路

1. 线段树的解法就非常暴力，没啥好讲的，需要 lazy 节点之类的，比较麻烦。查分数组的思路就非常简单，直接讲每个区间 $[l,r]$ ,在 $l，r+1$ 处进行进行标记即可，统计时依次统计即可。

• 时间复杂度：时间复杂度为 $O(m + n)$，其中 $m$ 为 $shift$ 数组的长度，$n$ 为字符串的长度。
• 空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 表示字符串的长度。

代码

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.size();
        int m = shifts.size();
        vector<int> cnt(n + 1, 0);
        for (int i = 0; i < m; i++) {
            if (shifts[i][2] == 0) {
                cnt[shifts[i][0]]--;
                cnt[shifts[i][1] + 1]++;
            } else {
                cnt[shifts[i][0]]++;
                cnt[shifts[i][1] + 1]--;
            }
        }
        int curr = 0;
        for (int i = 0; i < n; i++) {
            curr += cnt[i];
            s[i] = 'a' + (s[i] - 'a' + curr%26 + 26)%26;
        }
        return s;
    }
};

6159. 删除操作后的最大子段和

题目

给你两个下标从 0 开始的整数数组 nums 和 removeQueries ，两者长度都为 n 。对于第 i 个查询，nums 中位于下标 removeQueries[i] 处的元素被删除，将 nums 分割成更小的子段。

一个 子段 是 nums 中连续 正 整数形成的序列。子段和 是子段中所有元素的和。

请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]是第 i 次删除操作以后的 最大 子段和。

注意：一个下标至多只会被删除一次。

示例 1：

输入：nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
输出：[14,7,2,2,0]
解释：用 0 表示被删除的元素，答案如下所示：
查询 1 ：删除第 0 个元素，nums 变成 [0,2,5,6,1] ，最大子段和为子段 [2,5,6,1] 的和 14 。
查询 2 ：删除第 3 个元素，nums 变成 [0,2,5,0,1] ，最大子段和为子段 [2,5] 的和 7 。
查询 3 ：删除第 2 个元素，nums 变成 [0,2,0,0,1] ，最大子段和为子段 [2] 的和 2 。
查询 4 ：删除第 4 个元素，nums 变成 [0,2,0,0,0] ，最大子段和为子段 [2] 的和 2 。
查询 5 ：删除第 1 个元素，nums 变成 [0,0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。
所以，我们返回 [14,7,2,2,0] 。

示例 2：

输入：nums = [3,2,11,1], removeQueries = [3,2,1,0]
输出：[16,5,3,0]
解释：用 0 表示被删除的元素，答案如下所示：
查询 1 ：删除第 3 个元素，nums 变成 [3,2,11,0] ，最大子段和为子段 [3,2,11] 的和 16 。
查询 2 ：删除第 2 个元素，nums 变成 [3,2,0,0] ，最大子段和为子段 [3,2] 的和 5 。
查询 3 ：删除第 1 个元素，nums 变成 [3,0,0,0] ，最大子段和为子段 [3] 的和 3 。
查询 5 ：删除第 0 个元素，nums 变成 [0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。
所以，我们返回 [16,5,3,0] 。

提示：

• n == nums.length == removeQueries.length
• 1 <= n <= 105
• 1 <= nums[i] <= 109
• 0 <= removeQueries[i] < n
• removeQueries 中所有数字 互不相同 。

地址

https://leetcode.cn/contest/biweekly-contest-85/problems/maximum-segment-sum-after-removals/

题意

二分查找或者并查集

思路

1. 直接模拟的思路非常简单，也非常暴力。直接按照题目思路要求，每次将分段进行拆分即可。我们用一个 treemap 保存所有的分段信息，用一个 treemap 保存当前所有数组的中的分段和的统计。每次我们在 treemap 中查找给定的区间 $[x,x]$ 匹配的分段 $[l,r]$ ，然后将分段拆分成 $[l,x-1],[x+1,r]$ ,并从 map 中删除分段 $[l,r]$, 在 treemap 删除 $sum[l,r]$, 并同时添加 $sum[l,x-1], sum[x+1,r]$, 非常简单的模拟即可。

• 时间复杂度：$O(m \log m)$，其中 $m$ 表示数组的长度。

• 空间复杂度：$O(m)$，其中 $m$ 表示数组的长度。

2. 典型的并查集的操作。我们从后往前恢复数组，就可以看到实际为该数组的恢复过程，此时就联想到用并查集，思路非常简单，感觉是个经典题目，虽然不是特别难的题目。每次恢复 $x$ 时：

• 查看 $x$ 的左边位置 $x-1$ 是否已经恢复，如果已经恢复，则将两个位置进行合并；
• 查看 $x$ 的右边位置 $x+1$ 是否已经恢复，如果已经恢复，则将两个位置进行合并；
• 每次查询集合 $x$ 所在的集合的元素的和，更新当前的最大值即可；

时间复杂度分析：

• 时间复杂度：$O(n \times \alpha(n))$，其中 $n$ 表示数组的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度。

代码

• 二分查找

  class Solution { public: vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) { int n = nums.size(); vector<long long> sum(n + 1); for (int i = 0; i < n; i++) { sum[i+1] = sum[i] + nums[i]; } map<pair<int,int>, long long> cnt; map<long long, int> now; cnt[make_pair(n-1, 0)] = sum[n]; now[sum[n]]++; int m = removeQueries.size(); vector<long long> ans(m); for (int i = 0; i < m - 1; i++) { int x = removeQueries[i]; auto it = cnt.lower_bound({x,0}); int r = it->first.first; int l = it->first.second; long long s = it->second; cnt.erase(it); now[s]--; if(now[s] == 0) { now.erase(s); } if (x > l) { cnt[make_pair(x - 1, l)] = sum[x] - sum[l]; now[sum[x] - sum[l]]++; } if (x < r) { cnt[make_pair(r, x + 1)] = sum[r+1] - sum[x+1]; now[sum[r+1] - sum[x+1]]++; } ans[i] = now.rbegin()->first; } return ans; } };

• 并查集

  class Solution { public: int find(vector<int> &f, int x) { while (x != f[x]) { x = f[x]; } return x; } void uni(vector<int> &f, vector<long long> &sum, int x, int y) { int fx = find(f, x); int fy = find(f, y); f[fx] = fy; sum[fy] += sum[fx]; } vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) { int n = nums.size(); long long curr = 0; vector<int> fa(n, -1); vector<long long> sum(n, 0); vector<long long> ans(n, 0); for (int i = n - 1; i >= 0; i--) { ans[i] = curr; int x = removeQueries[i]; fa[x] = x; sum[x] = nums[x]; if (x - 1 >= 0 && fa[x - 1] >= 0) { uni(fa, sum, x, x - 1); } if (x + 1 < n && fa[x + 1] >= 0) { uni(fa, sum, x, x + 1); } curr = max(curr, sum[find(fa, x)]); } return ans; } };

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

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