作者推荐
【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II
本文涉及知识点
LeetCode2167移除所有载有违禁货物车厢所需的最少时间
给你一个下标从 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 * 105
s[i] 为 ‘0’ 或 ‘1’
动态规划
直接枚举右拆，余下的看左拆或左拆+中间拆或中间拆 那个更划算。
动态的状态表示
dp[i] 记录 s[0,i) 左拆+中间拆的最少时间。
动态规划的转移方程
s[i] = ‘0’ dp[i+1]=dp[i]
s[i]=‘1’
{ d p [ i + 1 ] = d p [ i ] + 2 中间拆 d p [ i + 1 ] = i + 1 左拆 \begin{cases} dp[i+1] = dp[i]+2 & 中间拆 \\ dp[i+1] = i+1 & 左拆 \end{cases}{dp[i+1]=dp[i]+2dp[i+1]=i+1中间拆左拆
动态规划的填表顺序
i从小到大。由于只用到dp[i]和dp[i+1] ，可以精简成两个变成pre,cur。再次精简成一个变量。
动态规划的初始值
dp[0]=0。
动态规划的返回值
dp[i] + (n-i) 的最小值。
代码
核心代码
class Solution { public: int minimumTime(string s) { int n = s.length(); int iRet = n; int cur = 0; for (int i = 0; i < n; i++) { if ('1' == s[i]) { cur = min(i + 1, cur + 2); } iRet = min(iRet, cur + n - (i + 1)); } return iRet; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string s; { Solution sln; s= "1100101"; auto res = sln.minimumTime(s); Assert(res,5); } { Solution sln; s = "0010"; auto res = sln.minimumTime(s); Assert(res, 2); } { Solution sln; s = "00000110100111110001110111000000000"; auto res = sln.minimumTime(s); Assert(res, 26); } }
2023 年2月版
class Solution {
public:
int minimumTime(string s) {
vector vLeftMid,vRightMin;
{
int iAdd = 0;
int iMinLeft = 0;
for (int i = 0; i < s.length(); i++)
{
if (‘0’ == s[i])
{
continue;
}
iAdd += 2;
int iMin = min(i + 1, iMinLeft + iAdd );
vLeftMid.push_back(iMin);
iMinLeft = min(iMinLeft, iMin - iAdd);
}
}
{
int iAdd = 0;
int iMinRight = 0;
vector tmp;
for (int i = s.length() - 1; i >= 0;i–)
{
if (‘0’ == s[i])
{
continue;
}
iAdd += 2;
int iMin = min((int)s.length()-i, iMinRight + iAdd);
tmp.push_back(iMin);
iMinRight = min(iMinRight, iMin - iAdd);
}
vRightMin.assign(tmp.rbegin(), tmp.rend());
}
if (0 == vLeftMid.size())
{
return 0;
}
int iMin = min(vLeftMid.back(), vRightMin.front());
for (int i = 0; i + 1 < vLeftMid.size(); i++)
{
iMin = min(iMin, vLeftMid[i] + vRightMin[i + 1]);
}
return iMin;
}
};
2023年7月版
class Solution {
public:
int minimumTime(string s) {
m_c = s.length();
int iPreCanSub = 0;
std::queue<std::pair<int, int>> queIndexNum;// 将第index节车厢(及更左）移除节省的次数
{
int iNum = 0;//车厢数
for (int i = 0; i < s.length(); i++)
{
if (‘0’ == s[i])
{
continue;
}
iNum++;
const int iCanSub = iNum * 2 - (i + 1);//左移能够减少的次数
if (iCanSub > iPreCanSub)
{
queIndexNum.emplace(i, iCanSub);
iPreCanSub = iCanSub;
}
}
}
int iNum = 0;//车厢数
std::stack<std::pair<int, int>> staIndexNum;//将第index节车厢(及更右）移除节省的次数
{
int iPreCanSub = 0;
for (int i = s.length() - 1; i >= 0; i–)
{
if (‘0’ == s[i])
{
continue;
}
iNum++;
const int iCanSub = iNum * 2 - (s.length() - i);//右移能够减少的次数
if (iCanSub > iPreCanSub)
{
staIndexNum.emplace(i, iCanSub);
iPreCanSub = iCanSub;
}
}
}
int iMaxCanSub = iPreCanSub;
int iMaxLeftSub = 0;
while (staIndexNum.size())
{
while (queIndexNum.size() && (queIndexNum.front().first < staIndexNum.top().first))
{
iMaxLeftSub = queIndexNum.front().second;
queIndexNum.pop();
}
iMaxCanSub = max(iMaxCanSub, iMaxLeftSub + staIndexNum.top().second);
staIndexNum.pop();
}
return iNum * 2 - iMaxCanSub;
}
int m_c;
};
