【Leetcode Daily】1888使二进制字符串字符交替的最少反转次数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个由 0 和 1 组成的字符串，想把该字符串改造为交替字符串，也就是 0 和 1 交替，但是只能做两个操作，1. 把第一个字符放到最后； 2. 使任意位置字符反转（0和1）。求实现的最少操作二次数。

思路分享

• 挺绕的，让吃完火锅的脑子转不过来。不过通过滑动窗口能够优雅地解决。

  https://leetcode.cn/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/solutions/1/ding-chang-hua-dong-chuang-kou-bian-shi-dqfi2/

• 简单说明思路，就是要解决两个问题：如何模拟操作一以及如何模拟操作二。

• 对于第一个问题，如果真的不断地把第一个字符放最后，也不难，但字符串操作效率不高，通过加倍字符串，然后让窗口直接向后滑动就能模拟每种操作一的情况了。老样子，还是把滑动窗口模板放一下（【Leetcode Daily】1456定长子串中元音的最大数目）。

• 对于第二个问题，由于连续字符串只有两个情况，010101 和 101010，可以用两个变量，分别存储两种情况下，需要操作二的次数，比如对于 010101，那么下标模 2 为 0 的地方，数值也应为 0，当满足这个条件，对应的变量值就不变，但另外一种情况必定不满足，就加一。

代码解答（强烈建议自行解答后再看）

• 参考解决方案

class Solution {
public:
    int minFlips(string s) {
        int n = s.size();
        s = s + s; // 双倍，通过滑动窗口模拟操作一
        
        // 对于滑动窗口的每个值，要满足的字符串情况有两种 010101 和 101010
        int cur_num1 = 0;
        int cur_num2 = 0;// 这两个数字分别表示两种情况下，操作二的最小次数

        int ans = INT_MAX;

        for (int i = 0; i < 2*n; i++) {
            if ((i%2==0&&s[i]=='0')||(i%2==1&&s[i]=='1')) {
                cur_num1++;
            }
            else {
                cur_num2++;
            }

            if (i < n-1) continue; // 窗口大小应恰好为 n

            ans = min(ans, min(cur_num1, cur_num2));

            int drop_index = i-n+1;
            if ((drop_index%2==0&&s[drop_index]=='0')||(drop_index%2==1&&s[drop_index]=='1')) {
                cur_num1--;
            }
            else {
                cur_num2--;
            }
        }

        return ans;

    }
};