LeetCode 题解工作台
将字符串翻转到单调递增
如果一个二进制字符串，是以一些 0 （可能没有 0 ）后面跟着一些 1 （也可能没有 1 ）的形式组成的，那么该字符串是 单调递增 的。 给你一个二进制字符串 s ，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。 返回使 s 单调递增的最小翻转次数。 示例 1： 输入： s = "0011…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们可以先统计字符串 中 的个数，记为 。定义一个答案变量 ，初始时 $ans = tot$，表示将所有 变成 的翻转次数。 然后，我们可以枚举每个位置 ，将位置 及其左边的所有 变成 ，将位置 右边的所有 变成 ，计算这种情况下的翻转次数，即 $i + 1 - cur + tot - cur$，其中 表示位置 及其左边的 的个数，更新答案 $ans = \min(ans, …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。
给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。
返回使 s 单调递增的最小翻转次数。
示例 1：
输入：s = "00110" 输出：1 解释：翻转最后一位得到 00111.
示例 2：
输入：s = "010110" 输出：2 解释：翻转得到 011111，或者是 000111。
示例 3：
输入：s = "00011000" 输出：2 解释：翻转得到 00000000。
提示：
1 <= s.length <= 105s[i]为'0'或'1'
解题思路
方法一：前缀和 + 枚举
我们可以先统计字符串 中 的个数，记为 。定义一个答案变量 ，初始时 ，表示将所有 变成 的翻转次数。
然后，我们可以枚举每个位置 ，将位置 及其左边的所有 变成 ，将位置 右边的所有 变成 ，计算这种情况下的翻转次数，即 ，其中 表示位置 及其左边的 的个数，更新答案 。
最后返回答案 即可。
时间复杂度 ，其中 为字符串 的长度。空间复杂度 。
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
tot = s.count("0")
ans, cur = tot, 0
for i, c in enumerate(s, 1):
cur += int(c == "0")
ans = min(ans, i - cur + tot - cur)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should demonstrate a solid understanding of dynamic programming, especially state transitions.
- question_mark
Look for understanding of space optimization techniques in dynamic programming problems.
- question_mark
Candidate should discuss the importance of minimizing flip operations and trade-offs involved in the solution approach.
常见陷阱
外企场景- error
Failing to optimize space complexity by keeping unnecessary state values.
- error
Confusing the problem with one where no flips are allowed, missing the need for careful state transitions.
- error
Not correctly accounting for the two possible states ('0' end or '1' end) during the iteration, leading to incorrect results.
进阶变体
外企场景- arrow_right_alt
Consider variations with larger binary strings where optimized space handling is critical.
- arrow_right_alt
Extend the problem by introducing additional operations, such as flipping multiple characters at once.
- arrow_right_alt
Add constraints where the number of flips allowed is limited, adding complexity to the dynamic programming approach.