题目链接1888. 使二进制字符串字符交替的最少反转次数中等算法原理解法定长滑动窗口滑动窗口分类题目解析一轮复习——C.滑动窗口模型总结对于类型1的操作拿111000举例我们进行多次之后会发现一个规律而类型2的操作就是在插完一刀的位置开始进行翻转操作找最少翻转次数那么如何实现这一过程呢细节比如更新时cnt记录的是0101……模式的最小翻转次数那么n-cnt就是记录的1010……模式的最小翻转次数原理与下题相同A.每日一题——1758. 生成交替二进制字符串的最少操作数因为当前窗口内既可以改成0101……也可以改成1010……要取这两种模式的最小值min(cnt,n-cnt)思路一环滑动窗口会超时时间复杂度O(N²)我们可以枚举每个起始位置left然后用index(leftright)%n映射当前窗口[left,right]内的长为n的字符串通过right%2对应0101……的模式用cnt记录变成0101……需要翻转的最小次数缺点却很明显这会导致时间复杂度飙升到O(N²)而导致超时思路二字符串拼接滑动窗口细节遍历到2n-1而不是2n因为首尾共用的同一个写法一直接拼接17ms击败84.62%时间复杂度O(N)直接将两字符串拼接在一起成为新数组ss遍历更直观①如果不符合以开头为基准的模式0101……或1010……就用n^1进行‘0’和1的翻转②出窗口时为避免创建标记数组我们可以直接与原数组s进行比对因为出窗口时两者的left是一一对应的ss[left]!s[left]代表当时ss[left]进行过翻转写法二下标映射模拟拼接25ms击败55.13%时间复杂度O(N)与写法一不同我们也可以避免拼接字符串直接利用“正整数不是奇数就是偶数”的特点通过%2快速判断当前下标应为0还是应为1因为下标从0开始那么我们这种方式就对应着0101……的模式n-cnt就对应着1010……的模式这其中①s[right % n] % 2将字符0/1转为数字0/10的ASCII码48%201的49%21②出窗口时s[left] % 2 ! left % 2代表当时s[left]进行过翻转写法三位运算9ms击败98.08%时间复杂度O(N)我们可以用位运算对写法二的入窗口和出窗口进行优化我们要做的就是判断当前数s[x]是否模式0101……需要的数x是的话应该得到0不翻转否则得到1翻转对应入窗口时不等于就翻转累加翻转次数1对应出窗口时不等于就撤销当时的翻转-1核心位运算(s[x]^x)1判断在位置x上字符s[x]是否满足0101……的交替模式①s[x]0或1二进制最后一位恰好对应0和1②0101……模式里位置x应该是x%2也就是x的最后一位③s[x]^x如果字符和模式要求不一样结果最后一位就是1否则就是0④1只保留最后一位是1代表需要翻转是0代表无需翻转Java代码class Solution { //思路一环滑动窗口(会超时) public int minFlips(String ss) { char[] sss.toCharArray(); int ns.length,mincntn; for(int left0;leftn;left){//遍历每个开头位置 int cnt0;//记录变成0101……翻转次数 for(int right0;rightn;right){//映射到真实位置模拟当前窗口[left,right] int index(leftright)%n; char cs[index]; if(c!(right%20?0:1)) cnt; } //当前起点的最优解 mincntMath.min(mincnt,Math.min(cnt,n-cnt)); } return mincnt; } }class Solution { //思路二字符串拼接滑动窗口-写法一直接拼接 public int minFlips(String _s) { String _ss_s_s; char[] ss_ss.toCharArray(); char[] s_s.toCharArray(); int ns.length; int cnt0,mincntn;//最坏情况下翻转所有字符 for(int right1;right2*n-1;right){ //进窗口 if(ss[right]ss[right-1]){ cnt; ss[right]^1; } int leftright-n1; if(left0) continue; //更新 mincntMath.min(mincnt,Math.min(cnt,n-cnt)); //出窗口 if(ss[left]!s[left]) cnt--; } return mincntn?0:mincnt; } }class Solution { //思路二字符串拼接滑动窗口-写法二下标映射模拟拼接 public int minFlips(String ss) { char[] sss.toCharArray(); int ns.length; int mincntn,cnt0; //遍历到2n-1用right%n模拟拼接字符串ss的效果 for(int right0;right2*n-1;right){ //判断当前字符s[right%n]是否满足“0101……”模式 //s[right%n]%2:0→01→1 //进窗口 if(s[right%n]%2!right%2) cnt; int leftright-n1; if(left0) continue; //更新 //cnt当前窗口变成0101……的翻转次数 //n-cnt当前窗口变成1010……的翻转次数 mincntMath.min(mincnt,Math.min(cnt,n-cnt)); //出窗口 //如果之前翻转了现在要除去当时的翻转操作 if(s[left]%2!left%2) cnt--; } return mincnt; } }class Solution { //思路二字符串拼接滑动窗口-写法三位运算 public int minFlips(String ss) { char[] sss.toCharArray(); int ns.length; int mincntn,cnt0; for(int right0;right2*n-1;right){ //进窗口 cnt(s[right%n]^right)1; int leftright-n1; if(left0) continue; //更新 //cnt当前窗口变成0101……的翻转次数 //n-cnt当前窗口变成1010……的翻转次数 mincntMath.min(mincnt,Math.min(cnt,n-cnt)); //出窗口 //如果之前翻转了现在要除去当时的翻转操作 cnt-(s[left]^left)1; } return mincnt; } }