leetcode竞赛：85 场双周赛

双周赛"/>

leetcode竞赛：85 场双周赛

链接：/
日期：2022年08月20日
1.
定长滑动窗口

class Solution {
public:int minimumRecolors(string blocks, int k) {int n = blocks.size(), cnt = 0, res = 1000;for (int i = 0, j = 0; i < n; i++) {while (j < n && j - i < k) {if (blocks[j++] == 'W') cnt++;}if (j - i == k) res = min(res, cnt);if (blocks[i] == 'W') cnt--;}return res;}
};

暴力模拟

class Solution {
public:int secondsToRemoveOccurrences(string s) {int res = 0, n = s.size();while (true) {int flag = 0;for (int i = 1; i < n; i++) {if (s[i - 1] == '0' && s[i] == '1') {swap(s[i-1], s[i]);i++;flag = 1;}}if (!flag) break;res++;}return res;}
};

差分算法

class Solution {
public:string shiftingLetters(string s, vector<vector<int>>& shifts) {int n = s.size();vector<int> t(n + 1);for (auto &p:shifts) {int a = p[0], b = p[1], d = p[2];if (d == 0) d = -1;t[a] += d;t[b + 1] -= d;}for (int i = 1; i <= n; i++) {t[i] += t[i - 1];t[i - 1] = t[i - 1] % 26 + 26;char c = (s[i - 1] - 'a' + t[i - 1]) % 26 + 'a';s[i - 1] = c;}return s;}
};

逆向并查集 做法

class Solution {
public:typedef long long LL;vector<LL> s;vector<int> p;int find(int x) {if (p[x] != x) {p[x] = find(p[x]);}return p[x];}LL Union(int a, int b) {a = find(a), b = find(b);p[a] = b;s[b] += s[a];return s[b];}vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {vector<LL> res;int n = removeQueries.size();for (int i = 0; i < nums.size(); i++) {p.push_back(i);s.push_back(0);}LL mx = 0;for (int i = n - 1; i >= 0; i--) {res.push_back(mx);int x = removeQueries[i];s[x] = nums[x];if (x > 0 && s[x - 1]) mx = max(mx, Union(x, x - 1));if (x < n - 1 && s[x + 1]) mx = max(mx, Union(x, x + 1));mx = max(mx, s[x]);}reverse(res.begin(), res.end());return res;}
};

模拟列项正向维护分裂数组的最大值：二分，lower_bound

class Solution {
public:typedef long long LL;vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {int n = nums.size();vector<LL> f(n + 1), res;for (int i = 0; i < n; i++) {f[i + 1] = f[i] + nums[i];}set<int> st; st.insert(0); st.insert(n);multiset<long long> ms;ms.insert(f[n]);for (int pos : removeQueries) {auto i = st.upper_bound(pos);auto j = (i--);int L = *i, R = *j;ms.erase(ms.lower_bound(f[R] - f[L]));st.insert(pos);st.insert(pos + 1);ms.insert(f[pos] - f[L]);ms.insert(f[R] - f[pos + 1]);res.push_back(*ms.rbegin());}return res;}
};