LeetCode 题解工作台
生成交替二进制字符串的最少操作数
给你一个仅由字符 '0' 和 '1' 组成的字符串 s 。一步操作中，你可以将任一 '0' 变成 '1' ，或者将 '1' 变成 '0' 。 交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 "010" 是交替字符串，而字符串 "0100" 不是…
1
题型
7
代码语言
3
相关题
当前训练重点
简单 · String-driven solution strategy
答案摘要
根据题意，如果得到交替字符串 `01010101...` 所需要的操作数为 ，那么得到交替字符串 `10101010...` 所需要的操作数为 $n - \textit{cnt}$。 因此，我们只需要遍历一次字符串 ，统计出 的值，那么答案即为 $\min(\textit{cnt}, n - \textit{cnt})$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 String-driven solution strategy 题型思路
题目描述
给你一个仅由字符 '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 <= s.length <= 104s[i]是'0'或'1'
解题思路
方法一：一次遍历
根据题意，如果得到交替字符串 01010101... 所需要的操作数为 ，那么得到交替字符串 10101010... 所需要的操作数为 。
因此，我们只需要遍历一次字符串 ，统计出 的值，那么答案即为 。
时间复杂度 ，其中 为字符串 的长度。空间复杂度 。
class Solution:
def minOperations(self, s: str) -> int:
cnt = sum(c != '01'[i & 1] for i, c in enumerate(s))
return min(cnt, len(s) - cnt)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
The candidate can identify and count mismatches efficiently.
- question_mark
The candidate recognizes that there are only two possible alternating patterns to consider.
- question_mark
The candidate applies a linear time complexity approach to solve the problem.
常见陷阱
外企场景- error
Failing to consider both possible alternating patterns.
- error
Not efficiently counting mismatches, leading to excessive time complexity.
- error
Confusing the concept of alternating strings with other string patterns, missing the specific alternating condition.
进阶变体
外企场景- arrow_right_alt
Modify the problem to consider strings with additional characters or constraints.
- arrow_right_alt
Extend the problem to allow other operations besides changing characters.
- arrow_right_alt
Challenge candidates with larger input sizes and more complex constraints.