状态建图最短路

lc3399二分(左闭右开) 贪心检查求在最多 numOps 次修改下字符串能变成的「最小连续相同段长度」class Solution {public:int minLength(string s, int numOps) {int n s.length();auto check [](int m) - bool {int cnt 0;if (m 1) {// 改成 0101...for (int i 0; i n; i) {// 如果 s[i] 和 i 的奇偶性不同cnt 加一cnt (s[i] ^ i) 1;}// n-cnt 表示改成 1010...cnt min(cnt, n - cnt);} else {int k 0;for (int i 0; i n; i) {k;// 到达连续相同子串的末尾if (i n - 1 || s[i] ! s[i 1]) {cnt k / (m 1);k 0;}}}return cnt numOps;};//左闭右开int l 1, r n;while (l r) {int mid l (r - l) / 2;if(check(mid))r mid;elselmid1;}return l;}};lc3579预处理子串变换转移的最小操作 后dp把字符串 s 变成 t可分段、可翻转每段求用最少替换次数完成的总代价区间 DP 贪心匹配计算最小操作数class Solution {public:int minOperations(string s, string t){int n s.size();//预处理子串变换需要的最少操作次数auto get [](string a,string b)-int{int ans a.size();vectorbool vis(ans,false);for(int i 0;i a.size();i){if(vis[i]) continue;if(a[i] b[i]){ans--; vis[i] true;}else{char x a[i],y b[i];for(int j i 1;j a.size();j){if(a[j] y b[j] x !vis[j]){ans--;vis[i] vis[j] true;break;}}}}return ans;};vector sum(n,vectorint(n,INT_MAX / 2));for(int i 0;i n;i){for(int j i;j n;j){string s1 s.substr(i,j - i 1),t1 t.substr(i,j - i 1);int res get(s1,t1);if(j i){reverse(s1.begin(),s1.end());res min(res,get(s1,t1) 1);}sum[i][j] res;}}vectorint dp(n 1,INT_MAX / 2);dp[0] 0;for(int i 1;i n;i){for(int j i - 1;j 0;j--){dp[i] min(dp[i],dp[j] sum[j][i - 1]);}}return dp[n];}};lc3666BFS 最短路 奇偶剪枝 有序集合优化从当前 0 的个数出发用 BFS 求每次翻转最多 k 个字符、恰好把所有字符变成 10 的个数为 0的最少操作次数用 set 按奇偶性维护未访问状态快速批量扩展合法转移class Solution {public:int minOperations(string s, int K){int n s.size();int dis[n 1];memset(dis, -1, sizeof(dis));// 按奇偶性把所有节点加入有序集合setint st[2];for (int i 0; i n; i) st[i 1].insert(i);// 计算当前字符串有几个 0这是我们的出发节点int S 0;for (char c : s) if (c 0) S;queueint q;q.push(S); dis[S] 0; st[S 1].erase(S);while (!q.empty()) {int sn q.front(); q.pop();// 计算变化的范围// 最多选 min(K, sn) 个 0以及最多选 min(K, n - sn) 个 1int l min(K, sn);l (K - l) - l;int r min(K, n - sn);r r - (K - r);// 将指定范围里还未访问过的节点取出来然后删除auto tmp st[(sn l) 1];auto it tmp.lower_bound(sn l);while (it ! tmp.end()) {if (*it sn r) break;q.push(*it);dis[*it] dis[sn] 1;tmp.erase(it);}}return dis[0];}};