力扣(LeetCode)1758. 生成交替二进制字符串的最少操作数(C++)

模拟

我们最终串只有两种形态
① $1010101\dots$ 偶数位全 $1$ ，奇数位全 $0$ ，
② $0101010\dots$ 偶数位全 $0$ ，奇数位全 $1$ ，
我们统计将偶数位全变成 $1$ ，奇数位全变成 $0$ 的操作次数，对应①的情况。
发现将偶数位全变成 $0$ ，奇数位全变成 $1$ 的操作次数，等于总长度减去变①的操作次数。
统计一种操作次数，和总长度 $-$ 操作次数 取最小值，即为最少操作数。

class Solution {
public:
    int minOperations(string s) {
        int ans = 0;
        for(int i = 0;i<s.size();i++)
            if(s[i]-'0'==(i&1))
                ans++;
        return min(ans,(int)s.size()-ans);
    }
};
1
2
3
4
5
6
7
8
9
10

1. 时间复杂度 : $O(n)$ ， $n$ 是字符串 ，遍历字符串时间复杂度 $O(n)$ 。
2. 空间复杂度 : $O(1)$ ，只使用了常量级空间。

AC