Question

2167. 移除所有载有违禁货物车厢所需的最少时间

English Version

题目描述

给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢 不 含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。

作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：

1. 从列车 左 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
2. 从列车 右 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
3. 从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。

返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。

注意，空的列车车厢序列视为没有车厢含违禁货物。

 

示例 1：

输入：s = "_11_00_1_0_1_"
输出：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 = "00_1_0"
输出：2
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间是 3.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从右端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
总时间是 2.

2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。

 

提示：

• 1 <= s.length <= 2 * 105
• s[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:]))

class Solution {
  public int minimumTime(String s) {
    int n = s.length();
    int[] pre = new int[n + 1];
    int[] suf = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      pre[i + 1] = s.charAt(i) == '0' ? pre[i] : Math.min(pre[i] + 2, i + 1);
    }
    for (int i = n - 1; i >= 0; --i) {
      suf[i] = s.charAt(i) == '0' ? suf[i + 1] : Math.min(suf[i + 1] + 2, n - i);
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 1; i <= n; ++i) {
      ans = Math.min(ans, pre[i] + suf[i]);
    }
    return ans;
  }
}

class Solution {
public:
  int minimumTime(string s) {
    int n = s.size();
    vector<int> pre(n + 1);
    vector<int> suf(n + 1);
    for (int i = 0; i < n; ++i) pre[i + 1] = s[i] == '0' ? pre[i] : min(pre[i] + 2, i + 1);
    for (int i = n - 1; ~i; --i) suf[i] = s[i] == '0' ? suf[i + 1] : min(suf[i + 1] + 2, n - i);
    int ans = INT_MAX;
    for (int i = 1; i <= n; ++i) ans = min(ans, pre[i] + suf[i]);
    return ans;
  }
};

func minimumTime(s string) int {
  n := len(s)
  pre := make([]int, n+1)
  suf := make([]int, n+1)
  for i, c := range s {
    pre[i+1] = pre[i]
    if c == '1' {
      pre[i+1] = min(pre[i]+2, i+1)
    }
  }
  for i := n - 1; i >= 0; i-- {
    suf[i] = suf[i+1]
    if s[i] == '1' {
      suf[i] = min(suf[i+1]+2, n-i)
    }
  }
  ans := 0x3f3f3f3f
  for i := 1; i <= n; i++ {
    ans = min(ans, pre[i]+suf[i])
  }
  return ans
}