Leetcode 第85场 双周赛 复盘

Leetcode 第 85 场双周赛

第一次参加双周赛，第二次AK，感觉写的时候还是迷迷瞪瞪，写完三题200多名（主要第二题python很方便秒过），AK完罚时从4百多掉到500多。都没有什么复杂的算法，主要看能不能想到，哎，心态很重要。

第三题：主要思想是差分
第四题：前缀和和二分 用上set，map，priority_queue 辅助

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

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int ans = 0, n = blocks.size(), l = 0, r = k, tmp =0;
        for(int i=0;i<k;i++) if(blocks[i]=='W') tmp++;
        ans = tmp;
        while(r<n) {
            if(blocks[r]=='W') tmp++;
            if(blocks[l]=='W') tmp--;
            r++;l++;
            ans = min(tmp,ans);
        }
        return ans;
    }
};

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

class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int:
        ans = 0
        while "01" in s:
            ans+=1
            s = s.replace("01","10")
        return ans 

6158. 字母移位 II

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.size();
        map<int,int> mp;
        for(int i=0;i<shifts.size();i++) {
            mp[shifts[i][0]] += shifts[i][2]==1?1:-1;
            mp[shifts[i][1]+1] += shifts[i][2]==1?-1:1;
        }
        auto it = mp.begin();
        int dis = 0,ix = 0;
        while(it!=mp.end()){
            while(ix<n && ix < it->first) s[ix] = (s[ix] -'a' + dis + 26 )%26 + 'a', ix++;
            dis += (it->second + 26)%26;
            it++;
        }
        return s;
    }
};

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

class Solution {
public:
    vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
        int n = nums.size();
        vector<long long> pre(n+1,0);
        vector<long long> ans(n);

        for(int i=0;i<n;i++) pre[i+1] = nums[i] + pre[i];
        
        set<int> se;
        map<long long,long long> mp;
        priority_queue<long long,vector<long long>,less<>> pq;
        
        se.insert(0);
        se.insert(n+1);
        
        mp[pre[n]-pre[0]] = 1;
        pq.push(pre[n]-pre[0]);
        
        for(int i=0;i<n;i++) {
            int a = removeQueries[i] + 1;
            se.insert(a);
            auto it =  se.lower_bound(a);
            it--;
            int x = *it; it++;it++;
            int y = *it;
            mp[pre[y-1]-pre[x]] -= 1;
            if(a!=x+1) mp[pre[a-1] - pre[x]] += 1, pq.push(pre[a-1] - pre[x]);
            if(a!=y-1) mp[pre[y-1] - pre[a]] += 1, pq.push(pre[y-1] - pre[a]);
            
            while(!pq.empty()&&mp[pq.top()]==0) pq.pop();
            if(!pq.empty()) ans[i] = pq.top();
            else ans[i] = 0;
        }
        return ans;
        
    }
};