题目描述

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

给你一个仅由字符 '0' 和 '1' 组成的字符串 s。一步操作中，你可以将任一 '0' 变成 '1'，或者将 '1' 变成 '0'。

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

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

示例 1：

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

示例 2：

• 输入：s = "10"
• 输出：0
• 解释：s 已经是交替字符串

示例 3：

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

解题思路

核心观察

交替二进制字符串只有两种可能的模式：

1. 模式 A：以 0 开头，即 "010101..."（偶数位置为 0，奇数位置为 1）
2. 模式 B：以 1 开头，即 "101010..."（偶数位置为 1，奇数位置为 0）

贪心策略

由于只有两种目标模式，我们可以：

1. 计算将字符串转换为模式 A 需要的操作数
2. 计算将字符串转换为模式 B 需要的操作数
3. 取两者的最小值

关键发现：如果转换为模式 A 需要 x 次操作，那么转换为模式 B 需要 len(s) - x 次操作。

原因：每个位置要么符合模式 A，要么符合模式 B，两者互补。

算法步骤

1. 遍历字符串，统计不符合模式 A（以 0 开头）的位置数量，记为 ans
2. 模式 A 的期望：偶数位置为 0，奇数位置为 1
3. 如果 s[i] 不等于 i % 2，说明该位置需要修改
4. 返回 min(ans, len(s) - ans)，即两种模式中操作数较少的那个

代码实现

方法一：贪心算法（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func minOperations(s string) int {
    ans := 0
    // 统计不符合"010101..."模式的位置数
    for i, v := range s {
        if int(v-'0') != i%2 {
            ans++
        }
    }
    // 返回两种模式中操作数较少的
    return min(ans, len(s)-ans)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

方法二：显式计算两种模式（备选）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func minOperations(s string) int {
    pattern1, pattern2 := 0, 0
    
    for i := 0; i < len(s); i++ {
        // 模式1: "010101..."
        if i%2 == 0 {
            if s[i] != '0' {
                pattern1++
            }
        } else {
            if s[i] != '1' {
                pattern1++
            }
        }
        
        // 模式2: "101010..."
        if i%2 == 0 {
            if s[i] != '1' {
                pattern2++
            }
        } else {
            if s[i] != '0' {
                pattern2++
            }
        }
    }
    
    return min(pattern1, pattern2)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

核心细节

1. 模式互补性：两种模式的操作数之和等于字符串长度，因此只需计算一种模式
2. 位置判断：使用 i % 2 判断当前位置应该是 0 还是 1
3. 字符转换：v - '0' 将字符 '0' 或 '1' 转换为整数 0 或 1
4. 贪心正确性：由于每个位置独立，局部最优即全局最优

复杂度分析

方法一

• 时间复杂度：O(n)，只需遍历字符串一次
• 空间复杂度：O(1)，只使用常量额外空间

方法二

• 时间复杂度：O(n)，遍历字符串一次
• 空间复杂度：O(1)，只使用常量额外空间

方法对比

推荐使用方法一，代码更简洁高效。

示例分析

示例 1：s = "0100"

模式 A（”0101”）：

• 位置 0：'0' 期望 '0' ✓
• 位置 1：'1' 期望 '1' ✓
• 位置 2：'0' 期望 '0' ✓
• 位置 3：'0' 期望 '1' ✗（需要修改）
• 操作数：1

模式 B（”1010”）：

• 需要修改位置 0、1、2，共 3 次操作

结果：min(1, 3) = 1

示例 3：s = "1111"

模式 A（”0101”）：

• 位置 0、2 需要修改，共 2 次操作

模式 B（”1010”）：

• 位置 1、3 需要修改，共 2 次操作

结果：min(2, 2) = 2

总结

这道题的关键点：

• 理解交替字符串只有两种模式："010101..." 和 "101010..."
• 利用模式互补性：两种模式的操作数之和等于字符串长度
• 贪心策略：只需计算一种模式的操作数，另一种自动得出
• 一次遍历：通过 i % 2 判断期望值，统计不匹配的位置数