绍兴建设网站,怎么注册商标品牌,网站的交互性,wordpress 静态化 cos作者推荐
【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II
本文涉及知识点
动态规划汇总
LeetCode2167移除所有载有违禁货物车厢所需的最少时间
给你一个下标从 0 开始的二进制字符串 s #xff0c;表示一个列车车厢序列。s[i] ‘0’ 表示第 i 节车厢 不 含违…作者推荐
【深度优先搜索】【树】【有向图】【推荐】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[i1]dp[i] s[i]‘1’ { d p [ i 1 ] d p [ i ] 2 中间拆 d p [ i 1 ] i 1 左拆 \begin{cases} dp[i1] dp[i]2 中间拆 \\ dp[i1] i1 左拆 \end{cases} {dp[i1]dp[i]2dp[i1]i1中间拆左拆
动态规划的填表顺序
i从小到大。由于只用到dp[i]和dp[i1] 可以精简成两个变成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;}
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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::queuestd::pairint, 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::stackstd::pairint, 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; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
