算法刷题打卡第30天：生成交替二进制字符串的最少操作数

生成交替二进制字符串的最少操作数

难度：简单
给你一个仅由字符 ‘0’ 和 ‘1’ 组成的字符串 s 。一步操作中，你可以将任一 ‘0’ 变成 ‘1’ ，或者将 ‘1’ 变成 ‘0’ 。

交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 “010” 是交替字符串，而字符串 “0100” 不是。

返回使 s 变成 交替字符串 所需的 最少 操作数。

示例 1：

输入：s = "0100"
输出：1
解释：如果将最后一个字符变为 '1' ，s 就变成 "0101" ，即符合交替字符串定义。
1
2
3

示例 2：

输入：s = "10"
输出：0
解释：s 已经是交替字符串。
1
2
3

示例 3：

输入：s = "1111"
输出：2
解释：需要 2 步操作得到 "0101" 或 "1010" 。
1
2
3

解法一：模拟

思路：
根据题意，经过多次操作，s 可能会变成两种不同的交替二进制字符串，即：

• 开头为 0，后续交替的字符串；
• 开头为 1，后续交替的字符串。

注意到，变成这两种不同的交替二进制字符串所需要的最少操作数加起来等于 s 的长度，我们只需要计算出变为其中一种字符串的最少操作数，就可以推出另一个最少操作数，然后取最小值即可。

时间复杂度： $O(n)$，其中 $n$ 为输入 $s$ 的长度，仅需遍历一遍字符串。
空间复杂度： $O(1)$，只需要常数额外空间。

写法一：两种情况都模拟

class Solution:
    def minOperations(self, s: str) -> int:
        step1 = 0
        step2 = 0
        for i, x in enumerate(s):
            if i % 2 == 1:
                if x == "1":
                    step1 += 1
                else:
                    step2 += 1
            else:
                if x == "1":
                    step2 += 1
                else:
                    step1 += 1
        return min(step1, step2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

写法二：如思路中所提，只模拟一种情况（官方写法）

class Solution:
    def minOperations(self, s: str) -> int:
        step = sum(i % 2 != int(x) for i, x in enumerate(s))
        return min(step, len(s)-step)
1
2
3
4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-changes-to-make-alternating-binary-string