力扣-1758. 生成交替二进制字符串的最少操作数

题目描述

思路及实现

土方法遍历

不想思考？那就遍历吧。设置两个bool变量和两个计数变量，遇到需要修改的地方计数加一，最后返回小的那个就好了。
这里两个bool变量分别对应01和10的情况，每循环一次都修改一次就能达到目的。

class Solution:
    def minOperations(self, s: str) -> int:
        flag_a = False
        flag_b = True
        cnt_a = 0
        cnt_b = 0
        for c in s:
            if flag_a == int(c):
                cnt_a += 1
            if flag_b == int(c):
                cnt_b += 1
            flag_a = not flag_a
            flag_b = not flag_b
        return min(cnt_a, cnt_b)

找规律

这不都知道字符串最后无非都会变成0101...和1010...的情况了嘛，可以根据这个知道，如果其中一种情况需要改变的次数为cnt_a，那么另外一种情况需要改变的次数就是cnt_b = len(s) - cnt_a，这样就能降低点复杂度。
我们又能知道，0和1无非就是奇数和偶数，根据遍历时候的每一位索引余2的结果来产生0和1又可以降低一点复杂度。

class Solution:
    def minOperations(self, s: str) -> int:
        cnt = 0
        n = len(s)
        for i, c in enumerate(s):
            if int(c) != i % 2:
                cnt += 1
        return min(cnt, n - cnt)

---

希望本文章能够帮到您~