LeetCode第 85 场双周赛总结

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

  简单题，维护一个长度为7的滑动窗口，保存窗口中’W’出现的最少次数。

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int n = blocks.size();
        int w = 0;
        int ans=n;
        for(int i =0;i<k;i++){
            if(blocks[i]=='W')
                w++;
        }
        ans = min(ans,w);
        int left = 1,right = k;
        while(right<n){
            if(blocks[left-1]=='W'){
                w--;
            }
            if(blocks[right]=='W'){
                w++;
            }
            ans=min(ans,w);
            right++;
            left++;
        } 
        return ans;
    }
};
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

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

  按照题目意思，暴力遍历即可

class Solution {
public:
    int secondsToRemoveOccurrences(string s) {
        int ans=0;
        int p1 = 0;
        int n = s.size();
        for(int i =0;i<n;i++){
            if(s[i]=='1') p1++;
        }
        while(1){
            int judge=0;
            for(int i =0;i<n;i++){
                if(s[i]=='0') break;
                judge++;
            }
            if(judge==p1) break;
            for(int i =0;i+1<n;i++){
                if(s[i]=='0'&&s[i+1]=='1'){
                    s[i]='1';
                    s[i+1]='0';
                    i++;
                }
            }
            ans++;   
        }
        return ans;
    }
};
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

3、字母移位 II

  用到了一个算法----差分数组。差分数组结合前缀和可以用来处理数组区间加减一个数的问题，附差分数组模板
  在本题中，shifts数组中的值[a,b,c]可以理解为，当c为1时，s[a,b]上的字符全部+1。当c为0时，s[a,b]上的字符全部+(-1)。本题首先使用差分数组处理shift，这样可以得到s中的每个字符应该改变多少。然后再便利一遍S即可。

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.size();
        int m = shifts.size();
        int diff[n+7];
        int res[n+7];
        
        memset(res,0,sizeof res);
        memset(diff,0,sizeof diff);
        
        for(int i=0;i<m;i++){
            if(shifts[i][2]==1){
                diff[shifts[i][0]]+=1;
                diff[shifts[i][1]+1]-=1;
            }
            else{
                diff[shifts[i][0]]-=1;
                diff[shifts[i][1]+1]+=1;
            }
        }
        res[0] = diff[0];
        for(int i=1;i<n;i++){
            res[i] = res[i-1]+diff[i];
            
        }
        for(int i =0;i<n;i++){
            int now = s[i]-97;
            now = now+res[i];
            while(now<0){
                now = now+26;
            }
            now = now%26;
            s[i] = now+97;
        }
        
        return s;
    }
};
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

差分数组常用模板

int a[N];//原数组 
int diff[N]; //差分数组
diff[0] = a[0];
for (int i = 1;i<n;i++)
	diff[i] = a[i]-a[i-1];
//区间修改
//如：对数组a, 区间[1,3]上所有的数加2,在[2,4]上的所有数减1。 
diff[1]+=2,diff[3+1]-=2;
diff[2]-=1,diff[4+1]+=1;
//对diff求前缀和可以即可得到修改后的a数组。
a[0] = diff[0];
for(int i=1;i<n;i++)
	a[i] = a[i-1] + diff[i]; 
1
2
3
4
5
6
7
8
9
10
11
12
13

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

  两种方法
  方法一、逆序处理+并查集
  逆序处理将删除每个元素改为逆序的增添元素，然后求连续子段最大值。使用并查集来维护子段之间的联通性，[l,pos-1], pos，[pos+1,r],当向序列中增加一个元素pos时，应该将pos左侧的区间和右侧区间连通，可以使用并查集处理。具体思路：没增添一个元素pos时，将pos和pos+1连通。分析：当增添pos-1时，已经将pos-1和pos连通到了一起，在处理pos时，可以实现pos左侧区间和右侧区间连通到一起。每增添一个元素都应更新一次答案，增添第i个元素的数组的最大子段和应该是max(ans[pos+1],s[to])，其中ans[pos+1]是上一个连通子段最大和，s[to]是当前连通子段的最大和。

class Solution {
public:
    int fa[100000+7];
    int find(int x){
        if(fa[x]!=x){
            fa[x]  = find(fa[x]);
        } 
        return fa[x];
    }
    long long s[100000+7];
    vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
        // memset(fa,0,sizeof fa);
        memset(s,0,sizeof s);
        int n = nums.size();
        for(int i =0;i<=n;i++){
            fa[i] = i;
        }
        vector<long long >ans(n+1,0); 
        // return ans;
        int m =removeQueries.size();
        
        for(int i = m-1;i>0;i--){
            int x = removeQueries[i];
            int to = find(x+1);
            fa[x] = to;
            s[to] +=(s[x] + nums[x]); 
            ans[i] = max(ans[i+1],s[to]);
        }
        vector<long long >res;
        for(int i=1;i<n;i++){
            res.push_back(ans[i]);
        }
        res.push_back(0);
        return res;
    }
};
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

方法二、前缀和+set区间维护
  前缀和数组从1到n表示，可以避免对边界的处理。使用set保存removeQueries的数组下标，初始化时将0和n+1增添到set中。每当删除一个pos时，会形成两个区间[L+1,pos-1]和[pos+1,R-1]，其中L是se中首个小于pos的小标，R是首个大于pos的下标，记 [L+1,pos-1]的子段和为sum1，[pos+1,R-1]的子段和为sum2。使用multiset保存每次形成的新子段和，同时pos还会将原子段和[L+1,R-1]给破坏掉，应同时将[L+1，R-1]的子段和删除掉，multiset中的最大值就是当前的最大子段和。

class Solution {
public:
    
    vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
        int n = nums.size();
        vector<long long >pre(n+2,0);
        for(int i=1;i<=n;i++) pre[i] = pre[i-1]+nums[i-1];
        set<int >se;
        se.insert(0);
        se.insert(n+1);
        multiset<long long >mse; 
        mse.insert(pre[n]);
        vector<long long >  ans;
        for(auto pos:removeQueries){
            pos++;
            
            int r = *se.lower_bound(pos);
            int l = *(--se.lower_bound(pos)); 
//          如果[l+1,r-1]这个值存在，将其删除
            se.insert(pos);
            mse.erase(mse.find(pre[r-1]-pre[l]));
            if(pos-1-l>0)
                mse.insert(pre[pos-1]-pre[l]);
            if(r-1-pos>0)
                mse.insert(pre[r-1]-pre[pos]);
            if (mse.empty()) ans.push_back(0);
            else ans.push_back(*prev(mse.end()));
        }
        return ans;
    }
};
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