本期总结：
-
涉及边界问题一定要自己检查看是否写错了，花1分钟检查总好过避免WA浪费5分钟
-
取余问题一定要注意负数的情况，必须要用加上Mod值直到大于0才能去取余
-
区间合并问题直接上并查集，别整更新左区间，更新右区间这种玩意，很容易错。
6156. 得到 K 个黑块的最少涂色次数 - 力扣（LeetCode）
很简单，滑动窗口，而且因为数量够小，直接暴力解决即可，不用做滑动窗口的特殊处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int minimumRecolors(String blocks, int k) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < blocks.length();i++) {
int count = 0;
int j = 0;
for (j = i; j < i+k && j < blocks.length();j++) {
if (blocks.charAt(j) == 'W') {
count++;
}
}
if (j != i+k) {
continue;
}
min = Math.min(count, min);
}
return min;
}
}
|
6157. 二进制字符串重新安排顺序需要的时间 - 力扣（LeetCode）
首先花了几分钟，推断出来最多变化n次（因为每处理一次至少前缀1会增加1个）
那么直接暴力O(n2)即可
但是因为边界处理写急了导致出错，我应该自己提交前再检查一下的
下面是错误的地方：
i+1==s.length()了，怎么可能添加11， 最多添加1个1才对。
正确答案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int secondsToRemoveOccurrences(String s) {
int res = 0;
while (true) {
StringBuilder sb = new StringBuilder();
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '0' && (i+1!=s.length() && s.charAt(i + 1) == '1')) {
sb.append("10");
i++;
count++;
} else if (s.charAt(i) == '0' && (i+1 == s.length() || s.charAt(i + 1) == '0')) {
sb.append("0");
} else if (s.charAt(i) == '1' && (i+1 != s.length() && s.charAt(i + 1) == '1')) {
sb.append("11");
i++;
} else {
sb.append("1");
}
}
s = sb.toString();
if (count == 0) {
return res;
}
res++;
}
}
}
|
6158. 字母移位 II - 力扣（LeetCode）
做过这类题，和那种任务流的题目类似
直接记录每个位置有多少起点，多少终点，根据情况进行加或者减。
但是对于移位的处理有点问题
1
2
3
4
5
| for (int i = 0; i < s.length();i++) {
count += startPlaces[i];
cs[i] = (char)((s.charAt(i) -'a' + count)%26 + 'a');
count += endPlaces[i];
}
|
看似很对， 却忘记了 负数取余也是负数。。
对负数取余应当通过加上26的倍数让他大于0才对。于是改成下面这样得到移位后的字符：
1
2
3
4
5
6
7
8
9
| char getMod(char c, int count) {
int num = c - 'a' + count;
if (num < 0) {
int mul = num / 26;
num += (mul+2)*26;
}
num %= 26;
return (char)(num + 'a');
}
|
结果还是错
因为我忘记了num是负数的时候，num/26也是负数。。应该要加一个Math.abs
正确做法如下getMod：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
char getMod(char c, int count) {
int num = c - 'a' + count;
if (num < 0) {
int mul = Math.abs(num / 26);
num += (mul+1)*26;
}
num %= 26;
return (char)(num + 'a');
}
public String shiftingLetters(String s, int[][] shifts) {
int[] startPlaces = new int[s.length()+1];
int[] endPlaces = new int[s.length()+1];
for (int i = 0; i < shifts.length;i++) {
int[] shift = shifts[i];
startPlaces[shift[0]] += (shift[2] == 1 ? 1: -1);
endPlaces[shift[1]] += (shift[2] == 0 ? 1: -1);
}
int count = 0;
char[] cs = new char[s.length()];
for (int i = 0; i < s.length();i++) {
count += startPlaces[i];
cs[i] = getMod(s.charAt(i), count);
count += endPlaces[i];
}
return new String(cs);
}
}
|
6159. 删除操作后的最大子段和 - 力扣（LeetCode）
、
这题又是做过类似的题，删点的题目可以反过来变成加点。
即从后往前逐步遍历，新增，逐步合并区间
结果还是用了错误的方式去更新，想着直接更新左右两个索引的sum值即可
实际上你要更新的应该是左边索引的最左点， 右边索引的最右点才对，而且每次合并都要修改左右的最左点或者最右点，非常麻烦，如下中间那4个if， 绕来绕去，注定要搞一次WA才能知道问题，非常不对劲：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
long[] sums = new long[nums.length];
long[] results = new long[nums.length];
int[] lefts = new int[nums.length];
int[] rights = new int[nums.length];
long maxNum = Long.MIN_VALUE;
for (int i = removeQueries.length-1;i>=1;i--) {
int index = removeQueries[i];
long leftSum = index-1 >= 0 ? sums[index-1] :0;
long rightSum = index + 1 < nums.length ? sums[index+1] : 0;
long sum = leftSum + rightSum + nums[index];
lefts[index] = rights[index] = index;
sums[index] = sum;
if (leftSum > 0) {
lefts[index] = lefts[index-1];
}
if (rightSum > 0) {
rights[index] = rights[index+1];
}
if (leftSum > 0) {
rights[lefts[index]] = rights[index];
sums[lefts[index]] = sum;
}
if (rightSum > 0) {
lefts[rights[index]] = lefts[index];
sums[rights[index]] = sum;
}
maxNum = Math.max(maxNum, sum);
results[i-1] = maxNum;
}
return results;
}
}
|
这种合并的题目就别取巧了， 直接并查集走起
注意并查集合并时，涉及val的合并， 在getParent中不需要更新val
在union中，注意顺序，p[p1]] = p2的话，说明p1的父亲变成了p2，那么应该是p2作为被加方，即sum[p2] += sum[p1]，反过来了
另外注意要先取变量，不要直接基于函数去搞，下面这样是错误的！因为第一步之后已经发生变成了：
1
2
3
4
| void union(int n1, int n2) {
parent[getParent(n1)] = getParent(n2);
sums[getParent(n2)] += sums[getParent(n1)];
}
|
应该是：
1
2
3
4
5
6
| void union(int n1, int n2) {
int p1 = getParent(n1);
int p2 = getParent(n2);
parent[p1] = p2;
sums[p2] += sums[p1];
}
|
并查集正确做法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
long[] sums;
int[] parent;
public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
long[] results = new long[nums.length];
sums = new long[nums.length];
long maxNum = Long.MIN_VALUE;
parent = new int[nums.length];
for (int i = 0; i < parent.length;i++) {
parent[i] = i;
}
for (int i = removeQueries.length-1;i>=1;i--) {
int index = removeQueries[i];
long leftSum = index-1 >= 0 ? sums[getParent(index-1)] :0;
long rightSum = index + 1 < nums.length ? sums[getParent(index+1)] : 0;
sums[index] = nums[index];
if (leftSum > 0) {
union(index-1, index);
}
if (rightSum > 0) {
union(index, index+1);
}
maxNum = Math.max(maxNum, sums[getParent(index)]);
results[i-1] = maxNum;
}
return results;
}
void union(int n1, int n2) {
int p1 = getParent(n1);
int p2 = getParent(n2);
parent[p1] = p2;
sums[p2] += sums[p1];
}
int getParent(int num) {
int p = parent[num];
if (p == num) {
return p;
} else {
p = getParent(p);
}
parent[num] = p;
return p;
}
}
|