class Solution {
public:
int minimumTime(string s) {
}
};
2167. 移除所有载有违禁货物车厢所需的最少时间
给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。
作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：
s[0]），用去 1 单位时间。s[s.length - 1]），用去 1 单位时间。返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。
注意，空的列车车厢序列视为没有车厢含违禁货物。
示例 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'原站题解
golang 解法, 执行用时: 52 ms, 内存消耗: 9.3 MB, 提交时间: 2023-09-17 11:47:43
func minimumTime(s string) int {
n := len(s)
suf := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
if s[i] == '0' {
suf[i] = suf[i+1]
} else {
suf[i] = min(suf[i+1]+2, n-i)
}
}
ans := suf[0]
pre := 0
for i, ch := range s {
if ch == '1' {
pre = min(pre+2, i+1)
ans = min(ans, pre+suf[i+1])
}
}
return ans
}
// 优化
func minimumTime2(s string) int {
n := len(s)
ans := n
pre := 0
for i, ch := range s {
if ch == '1' {
pre = min(pre+2, i+1)
}
ans = min(ans, pre+n-1-i)
}
return ans
}
func min(a, b int) int { if a > b { return b }; return a }
cpp 解法, 执行用时: 176 ms, 内存消耗: 52.5 MB, 提交时间: 2023-09-17 11:47:06
class Solution {
public:
int minimumTime(string s) {
int n = s.length();
vector<int> suf(n + 1);
for (int i = n - 1; i >= 0; --i)
suf[i] = s[i] == '0' ? suf[i + 1] : min(suf[i + 1] + 2, n - i);
int ans = suf[0], pre = 0;
for (int i = 0; i < n; ++i)
if (s[i] == '1') {
pre = min(pre + 2, i + 1);
ans = min(ans, pre + suf[i + 1]);
}
return ans;
}
// 优化
int minimumTime2(string s) {
int n = s.length(), ans = n, pre = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') pre = min(pre + 2, i + 1);
ans = min(ans, pre + n - 1 - i);
}
return ans;
}
};
java 解法, 执行用时: 47 ms, 内存消耗: 43.5 MB, 提交时间: 2023-09-17 11:46:28
class Solution {
public int minimumTime(String s) {
var n = s.length();
var suf = new int[n + 1];
for (var i = n - 1; i >= 0; --i)
suf[i] = s.charAt(i) == '0' ? suf[i + 1] : Math.min(suf[i + 1] + 2, n - i);
var ans = suf[0];
var pre = 0;
for (var i = 0; i < n; ++i)
if (s.charAt(i) == '1') {
pre = Math.min(pre + 2, i + 1);
ans = Math.min(ans, pre + suf[i + 1]);
}
return ans;
}
// 优化
public int minimumTime2(String s) {
var n = s.length();
var ans = n;
var pre = 0;
for (var i = 0; i < n; ++i) {
if (s.charAt(i) == '1') pre = Math.min(pre + 2, i + 1);
ans = Math.min(ans, pre + n - 1 - i);
}
return ans;
}
}
python3 解法, 执行用时: 1536 ms, 内存消耗: 24.8 MB, 提交时间: 2023-09-17 11:45:49
class Solution:
# 前后缀分解
def minimumTime(self, s: str) -> int:
n = len(s)
suf = [0] * (n + 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)
ans = suf[0]
pre = 0
for i, ch in enumerate(s):
if ch == '1':
pre = min(pre + 2, i + 1)
ans = min(ans, pre + suf[i + 1])
return ans
# 进一步优化，一次便利
def minimumTime2(self, s: str) -> int:
ans = n = len(s)
pre = 0
for i, ch in enumerate(s):
if ch == '1':
pre = min(pre + 2, i + 1)
ans = min(ans, pre + n - 1 - i)
return ans