LeetCode 题解工作台
移除所有载有违禁货物车厢所需的最少时间
给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。 s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。 作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个： 从列车 左 端移除一…
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution: def minimumTime(self, s: str) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。
作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：
- 从列车 左 端移除一节车厢（即移除
s[0]），用去 1 单位时间。 - 从列车 右 端移除一节车厢（即移除
s[s.length - 1]），用去 1 单位时间。 - 从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。
返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。
注意，空的列车车厢序列视为没有车厢含违禁货物。
示例 1：
输入：s = "1100101" 输出：5 解释： 一种从序列中移除所有载有违禁货物的车厢的方法是： - 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。 - 从右端移除一节车厢 1 次。所用时间是 1 。 - 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。 总时间是 2 + 1 + 2 = 5 。 一种替代方法是： - 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。 - 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。 总时间也是 2 + 3 = 5 。 5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。 没有其他方法能够用更少的时间移除这些车厢。
示例 2：
输入：s = "0010" 输出：2 解释： 一种从序列中移除所有载有违禁货物的车厢的方法是： - 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。 总时间是 3. 另一种从序列中移除所有载有违禁货物的车厢的方法是： - 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。 总时间是 2. 另一种从序列中移除所有载有违禁货物的车厢的方法是： - 从右端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。 总时间是 2. 2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。 没有其他方法能够用更少的时间移除这些车厢。
提示：
1 <= s.length <= 2 * 105s[i]为'0'或'1'
解题思路
方法一
class Solution:
def minimumTime(self, s: str) -> int:
n = len(s)
pre = [0] * (n + 1)
suf = [0] * (n + 1)
for i, c in enumerate(s):
pre[i + 1] = pre[i] if c == '0' else min(pre[i] + 2, i + 1)
for i in range(n - 1, -1, -1):
suf[i] = suf[i + 1] if s[i] == '0' else min(suf[i + 1] + 2, n - i)
return min(a + b for a, b in zip(pre[1:], suf[1:]))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the implementation of the DP array and string iteration, typically O(n) for both if suffix arrays are used. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on handling each '1' efficiently without redundant removals.
- question_mark
Explain why state transition captures optimal substructure.
- question_mark
Clarify how left, right, and middle operations are combined in DP.
常见陷阱
外企场景- error
Failing to consider the middle removal cost in DP updates.
- error
Updating DP states incorrectly leading to overcounting time.
- error
Assuming only left or right removals suffice without suffix calculations.
进阶变体
外企场景- arrow_right_alt
Compute minimum time when removal from ends costs different units.
- arrow_right_alt
Handle a sequence where illegal goods can appear consecutively in blocks.
- arrow_right_alt
Optimize for extremely large strings using rolling DP or prefix sums.