一个普通的排名
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
思路：
双指针
时间复杂度：O(n)
class Solution {public int minimumRecolors(String b, int k) {int min = k;for (int i = 0, j = 0, c = 0; i < b.length(); i++) {c += b.charAt(i) == 'W' ? 1 : 0;if (i - j == k) {c -= b.charAt(j++) == 'W' ? 1 : 0;}if (i - j + 1 == k)min = Math.min(min, c);}return min;}}
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’ 。
思路：
比赛的时候看到数据范围小，直接暴力做的
有线性做法
设f[i]为处理前i个字符所需的最小步数
考虑当前1左侧0的个数为pre则处理该1需要的操作数为min(pre, f[i - 1] + 1)
class Solution {public int secondsToRemoveOccurrences(String s) {StringBuilder sb = new StringBuilder();int n = s.length();int c = 0;for (int i = 0; i < n; i++) {if (s.charAt(i) == '0' && i + 1 < n && s.charAt(i + 1) == '1') {c++;sb.append("10");i++;} else {sb.append(s.charAt(i));}}if (c > 0) return 1 + secondsToRemoveOccurrences(sb.toString());else return 0;}}
class Solution {public int secondsToRemoveOccurrences(String s) {int n = s.length();int res = 0, pre = 0;for (int i = 0; i < n; i++) {if (s.charAt(i) == '0')pre++;else if (pre > 0)res = Math.max(pre, res + 1);}return res;}}
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 只包含小写英文字母。
思路：
差分数组 + 前缀和
class Solution {public String shiftingLetters(String s, int[][] shifts) {int n = s.length();int[] a = new int[n + 1];for (int[] p : shifts) {int l = p[0], r = p[1], x = p[2] == 1 ? 1 : -1;a[l] += x;a[r + 1] += -x;}StringBuilder sb = new StringBuilder();int sum = 0;for (int i = 0; i < n; i++) {sum += a[i];int x = ((s.charAt(i) - 'a' + sum) % 26 + 26) % 26;sb.append((char)(x + 'a'));}return sb.toString();}}
:::danger wa了一发，在第14行，一开始没处理负数 :::
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 中所有数字 互不相同 。
思路：
方法1：模拟
方法2：逆序并查集
class Solution {public long[] maximumSegmentSum(int[] nums, int[] r) {int n = nums.length;TreeSet<Integer> set = new TreeSet<>();set.add(1);set.add(n + 2);int m = r.length;long[] res = new long[m];long[] s = new long[n + 3];TreeMap<Long, Integer> had = new TreeMap<>();for (int i = 2; i <= n + 1; i++)s[i] = nums[i - 2] + s[i - 1];had.put(s[n + 1], 1);// System.out.println(Arrays.toString(s));for (int i = 0; i < m; i++) {int x = r[i] + 2;int pre = set.floor(x) + 1, last = set.ceiling(x) - 1;had.merge(s[last] - s[pre - 1], -1, Integer::sum);if (had.get(s[last] - s[pre - 1]) == 0)had.remove(s[last] - s[pre - 1]);set.add(x);had.merge(s[x - 1] - s[pre - 1], 1, Integer::sum);had.merge(s[last] - s[x], 1, Integer::sum);// System.out.println(had);res[i] = had.lastKey();}return res;}}
class Solution {public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {int n = nums.length;UnionFind uf = new UnionFind(n);long[] res = new long[n];for (int i = n - 1; i >= 0; i--) {res[i] = uf.max;uf.merge(removeQueries[i], nums[removeQueries[i]]);}return res;}}class UnionFind {int n;long max;int[] fa;long[] size;UnionFind(int n) {this.n = n;this.fa = new int[n];this.size = new long[n];for (int i = 0; i < n; i++)fa[i] = i;}void merge(int idx, int x) {size[idx] = x;if (idx + 1 < n && size[find(idx + 1)] > 0) {int px = find(idx), py = find(idx + 1);size[px] += size[py];fa[py] = px;}if (idx - 1 >= 0 && size[find(idx - 1)] > 0) {int px = find(idx), py = find(idx - 1);size[px] += size[py];fa[py] = px;}max = Math.max(max, size[find(idx)]);}int find(int x) {return x == fa[x] ? x : (fa[x] = find(fa[x]));}}
meituan-002. 小美的仓库整理
若有收获，就点个赞吧
0 人点赞
