【周赛复盘】力扣第 85 场双周赛

╰+哭是因爲堅強的太久メ 2023-09-28 21:26 81阅读 0赞

#### 目录 ####

*  1. 得到 K 个黑块的最少涂色次数
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  2. 二进制字符串重新安排顺序需要的时间
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  3. 字母移位 II
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  4. 删除操作后的最大子段和
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度

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

### 1）题目描述 ###

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

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

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

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

### 2）原题链接 ###

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

### 3）思路解析 ###

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

滑动窗口

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;
        }
    };

### 5）算法与时间复杂度 ###

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

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

### 1）题目描述 ###

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

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

### 2）原题链接 ###

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

### 3）思路解析 ###

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

### 4）模板代码 ###

暴力代码

class Solution {
        
        public int secondsToRemoveOccurrences(String s) {
        
            int ans=0;
            while (s.contains("01")){
        
                s=s.replace("01","10");
                ans++;
            }
            return ans; 
        }
    }

动规代码

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;
        }
    };

### 5）算法与时间复杂度 ###

算法：**暴力**  
  时间复杂度:暴力为 O ( n 2 ) O(n^2) O(n2)，动规为 O ( n ) O(n) 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][LeetCode.2381. _ II]

### 3）思路解析 ###

*   ( 1 ) (1) (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();
            }
        }

**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;
        }
    };

### 5）算法与时间复杂度 ###

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

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

### 1）题目描述 ###

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

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

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

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

### 2）原题链接 ###

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

### 3）思路解析 ###

*   ( 1 ) (1) (1)当删除一个下标后，一个子段和将会断开成为两个子段和，这是一个分离的状态，我们并不好维护，如果是将两个子段合并，那是我们想看到的，因为我们可以使用**并查集**去做到。
 *   ( 2 ) (2) (2)为此，我们可以逆向思维，倒着来删除数组，先假定数组全部为0，当删除第  i i i 个位置时，我们先获得此时并查集和最大的子段和作为答案，然后将第  i 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;
        }
    }

### 5）算法与时间复杂度 ###

算法：**并查集**  
  时间复杂度:暴力为 O ( n l o g n ) O(nlogn) O(nlogn)。

[LeetCode.6156. _ K]: https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/
[LeetCode.2380.]: https://leetcode.cn/problems/time-needed-to-rearrange-a-binary-string/
[LeetCode.2381. _ II]: https://leetcode.cn/problems/shifting-letters-ii/
[LeetCode.2382.]: https://leetcode.cn/problems/maximum-segment-sum-after-removals/