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

1）题目描述

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

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

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

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

2）原题链接

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

3）思路解析

$(1)$考虑到 $n$ 最大只有$100$，所以我们可以暴力枚举每个长度为k的区间，计算其黑色块的数目。设长度为k的区间，黑色块最多的数目为x，那么答案就是k-x，这样的时间复杂度为$O(n^2)$。
$(2)$假设n的范围达到1e5的级别，那我们就不能暴力枚举了，不过还是同样的思路，可以利用前缀和或者滑动窗口，在$O(1)$的时间复杂度获取每一个长度为 $k$ 的子数组的黑色块数组，这样扫一遍数组即可得到答案，时间复杂度为$O(n)$。

4）模板代码

暴力代码

class Solution {
    public int minimumRecolors(String s, int k) {
        int m=0;
        int n=s.length();
        for(int i=0;i+k-1<n;++i){
            int v=0;
            for(int j=i;j<=i+k-1;++j){
                if (s.charAt(j)=='B') v++;
            }
            m=Math.max(m,v);
        }
        return k-m;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

滑动窗口

class Solution {
public:
    int minimumRecolors(string s, int k) {
        int ans=0;
        int n=s.size();
        int v=0;
        for(int i=0,j=0;i<n;++i){
            v+=s[i]=='B';
            if(i-j+1>k){
                v-=s[j]=='B';
                j++;
            }
            if(i-j+1==k){
                ans=max(ans,v);
            }
        }
        return k-ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5）算法与时间复杂度

  算法：暴力枚举 滑动窗口 前缀和
  时间复杂度:$O(n^2)$或者$O(n)$均可。

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

1）题目描述

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

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

2）原题链接

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

3）思路解析

• $(1)$由于 $s$ 的长度 $n$ 最大只有1000，所以我们可以使用暴力枚举的方法。
• $(2)$当然这是一个经典的排队问题，我们的目的是让全部的1去到最左边，全部的0去到最右边。
  定义 $f[i]$ 为把 $s$ 前 $i$ 个字符完成移动所需的秒数。
  状态转移:
    1.当$s[i]==0$时，无需移动，则有$f[i]=f[i-1]$
    2.当$f[i]==1$时，要保证两个界限均成立，记$[0,i-1]$出现$0$的个数为$cn{t}_0$，那么$f[i]$最少为$cn{t}_0$，另一个是第 $i$ 个位的 $1$ 一定比其左边的1移动次数更多，最少要多$1$次，两者取大则为答案:
  $$f[i]=max(f[i-1],cn{t}_0)$$

4）模板代码

暴力代码

class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int ans=0;
        while (s.contains("01")){
            s=s.replace("01","10");
            ans++;
        }
        return ans; 
    }
}
1
2
3
4
5
6
7
8
9
10

动规代码

class Solution {
public:
    int secondsToRemoveOccurrences(string s) {
        int n=s.size();
        int f=0;
        int cnt=0;
        for(int i=0;i<n;++i){
            if(s[i]=='0'){
                cnt++;
            }else if(cnt){
                f=max(f+1,cnt);
            } 
        }
        return f;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5）算法与时间复杂度

  算法：暴力
  时间复杂度:暴力为$O(n^2)$，动规为$O(n)$。

3. 字母移位 II

1）题目描述

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

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

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

2）原题链接

LeetCode.2381. 字母移位 II

3）思路解析

• $(1)$每次变动是针对一段区间进行加减，很明显我们可以想到使用差分来记录字符的变化过程，最后还原差分数组后，针对每个位置字符的变动进行改动即可，由于字母表是环绕的，具体细节见代码实现。

4）模板代码

Java

class Solution {
     public String shiftingLetters(String s, int[][] shifts) {
        int n=s.length();
        int[] c=new int[n+10];
        for (int[] g:shifts){
            int start=g[0],end=g[1],v=g[2];
            if (v==1){
                c[start]++;
                c[end+1]--;
            }else{
                c[start]--;
                c[end+1]++;
            }
        }
        StringBuilder sb=new StringBuilder();
        for(int i=1;i<n+10;++i) c[i]+=c[i-1];
        for (int i = 0; i < n; i++) {
            int st=s.charAt(i)-'a';
                c[i]%=26;
                st+=c[i];
                st=(st+26)%26;
                sb.append((char)(st+'a'));
            }
            return sb.toString();
        }
    }

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

c++

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& arr) {
        int n=s.size();
        int cnt[n+10];
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<arr.size();++i){
            int a=arr[i][0],b=arr[i][1],v=arr[i][2];
            if(v) cnt[a]++,cnt[b+1]--;
            else cnt[a]--,cnt[b+1]++;
        }
        for(int i=1;i<n+10;++i) cnt[i]+=cnt[i-1];
        for(int i=0;i<n;++i){
             int st=s[i]-'a';
             cnt[i]%=26;
             st+=cnt[i];
             st=(st+26)%26;
             s[i]=(st+'a');
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5）算法与时间复杂度

  算法：差分
  时间复杂度:$O(n)$。

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

1）题目描述

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

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

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

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

2）原题链接

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

3）思路解析

• $(1)$当删除一个下标后，一个子段和将会断开成为两个子段和，这是一个分离的状态，我们并不好维护，如果是将两个子段合并，那是我们想看到的，因为我们可以使用并查集去做到。
• $(2)$为此，我们可以逆向思维，倒着来删除数组，先假定数组全部为0，当删除第 $i$ 个位置时，我们先获得此时并查集和最大的子段和作为答案，然后将第 $i$ 个位置的值变回本身的值，再将它和左右相邻非零的数合并。

4）模板代码

class Solution {
    int N=100100;
    int[] q=new int[N];
    long[] w=new long[N];
    boolean[] st=new boolean[N];
    int find(int x){
        if (x!=q[x]) q[x]=find(q[x]);
        return q[x];
    }
    public long[] maximumSegmentSum(int[] arr, int[] r) {
        int n=arr.length;
        long[] a=new long[n];
        for(int i=1;i<=n;++i){
            q[i]=i;
            w[i]=arr[i-1];
        }
        long max=0;
        for(int i=n-1;i>=0;--i){
            int x=r[i]+1;
            a[i]=max;
            st[x]=true;
            if (x>1){
                int l=x-1;
                if (st[l]){
                    x=find(x);
                    l=find(l);
                    q[x]=l;
                    w[l]+=w[x];
                    max=Math.max(max,w[l]);
                }
            }
            if (x<n){
                int l=x+1;
                if (st[l]){
                    x=find(x);
                    l=find(l);
                    q[x]=l;
                    w[l]+=w[x];
                    max=Math.max(max,w[l]);
                }
            }
            max=Math.max(max,w[find(r[i]+1)]);
        }
        return a;
    }
}
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

5）算法与时间复杂度

  算法：并查集
  时间复杂度:暴力为$O(nlogn)$。