无极网站,wordpress多张图片,wordpress 评论回推 地址,网站开发前台实训作者推荐
【动态规划】【广度优先】LeetCode2258:逃离火灾
本文涉及的基础知识点
二分查找算法合集 有序向量的二分查找#xff0c;初始化完成后#xff0c;向量不会修改。 双指针#xff1a; 用于计算子字符串是s的字符串的子系列。
题目
给你两个字符串 s 和 t 。 你…作者推荐
【动态规划】【广度优先】LeetCode2258:逃离火灾
本文涉及的基础知识点
二分查找算法合集 有序向量的二分查找初始化完成后向量不会修改。 双指针 用于计算子字符串是s的字符串的子系列。
题目
给你两个字符串 s 和 t 。 你可以从字符串 t 中删除任意数目的字符。 如果没有从字符串 t 中删除字符那么得分为 0 否则 令 left 为删除字符中的最小下标。 令 right 为删除字符中的最大下标。 字符串的得分为 right - left 1 。 请你返回使 t 成为 s 子序列的最小得分。 一个字符串的 子序列 是从原字符串中删除一些字符后也可以一个也不删除剩余字符不改变顺序得到的字符串。比方说 “ace” 是 “abcde” 的子序列但是 “aec” 不是。 示例 1 输入s “abacaba”, t “bzaa” 输出1 解释这个例子中我们删除下标 1 处的字符 “z” 下标从 0 开始。 字符串 t 变为 “baa” 它是字符串 “abacaba” 的子序列得分为 1 - 1 1 1 。 1 是能得到的最小得分。 示例 2 输入s “cde”, t “xyz” 输出3 解释这个例子中我们将下标为 0 1 和 2 处的字符 “x” “y” 和 “z” 删除下标从 0 开始。 字符串变成 “” 它是字符串 “cde” 的子序列得分为 2 - 0 1 3 。 3 是能得到的最小得分。 参数范围 1 s.length, t.length 105 s 和 t 都只包含小写英文字母。
分析
时间复杂度(nlogn)。枚举tRight时间复杂度O(n);二分查找tLeft时间复杂度O(logn)。令m_c是t的长度。tLeftleft-1,tRightright1。
变量解析
vLeft[i]x表示t[0,i]是s[0,x]子序列,x如果有多个值取最小值。如果x不存在为任意大于等于m_c的值。显然是升序。vRight[i]x表示t[t…)是s[x,…)子序列如果x有多个值取最大值。如果x不存在为任意小于0的值。
原理
将left和right直接的元素全部删除积分不会增加所以全删除。全删除后只有两种情况一不删除。二删除一处。t由两个部分组成。[0,tLeft]和[tRight,m_c)。如果左边为空,tLeft为-1;如果右边为空tRight为m_c。sRight 为vRight[tRight]sLeft是小于sRight中的最大值。这样确保[0,sLeft]和[sRight…)没有重叠部分。sLeft在vLeft中的下标就是tLefttLeft必须小于tRight否则[0,tLeft]和[tRight,m_c)会有重叠部分。
特殊情况
右边为空在初始化vRight的时候需要特殊处理后续操作不需要。 如果vRight[tRight]非法需要忽略。 tLeft为-1不需特殊处理就是左边为空。
代码
核心代码
class Solution {
public:int minimumScore(string s, string t) {m_c t.length();//vLeft[i]x表示t[0,i]是s[0,x]子序列,x如果有多个值取最小值。如果x不存在为任意大于等于m_c的值//vRight[i]x表示t[t...)是s[x,...)子序列如果x有多个值取最大值。如果x不存在为任意小于0的值。vectorint vLeft(m_c, m_c),vRight(m_c,-1);{for (int i 0, right0; i m_c; i){while ((right s.length()) (s[right] ! t[i])){right;}vLeft[i] right;}}{for (int i m_c - 1,lefts.length()-1; i 0; i--){while ((left 0) (s[left] ! t[i])){left--;}vRight[i] left--;}}int iRet m_c;vRight.emplace_back(s.length());//(right,m_c)为空不需要做特殊处理for (int tRight 0 ; tRight vRight.size(); tRight){const auto sRight vRight[tRight];if (sRight 0){continue;}//寻找第一个小于vRight[right]的索引int tLeft std::lower_bound(vLeft.begin(), vLeft.end(), sRight)- vLeft.begin()-1;tLeft min(tLeft, tRight - 1);iRet min(iRet, tRight - tLeft - 1);} return iRet;}int m_c;
};测试用例
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]);}
}templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}int main()
{string s, t; {Solution slu;s abacaba, t bzaa;auto res slu.minimumScore(s, t);Assert(1, res);}{Solution slu;s cde, t xyz;auto res slu.minimumScore(s, t);Assert(3, res);}{Solution slu;s adebddaccdcabaade, t adbae;auto res slu.minimumScore(s, t);Assert(0, res);}{Solution slu;s eceecbabe, t bdeaec;auto res slu.minimumScore(s, t);Assert(4, res);}//CConsole::Out(res);
}优化
第二轮循环可以和第三轮循环合并且改成双指针。可以直接用栈向量的出栈代替指针。第一轮寻找改成枚举s更方便。
class Solution {
public:int minimumScore(string s, string t) {m_c t.length();vectorint vLeft;for (int is 0; is s.length(); is){if ((vLeft.size() m_c) (s[is] t[vLeft.size()])){vLeft.emplace_back(is);}}int iRet m_c - vLeft.size(); //tRightm_cfor (int tRight m_c - 1,sRight s.length()-1 ; tRight 0; tRight--){while ((sRight 0) (s[sRight] ! t[tRight])){sRight--;}if (sRight 0){break;}while (vLeft.size() ((vLeft.back() sRight) || (vLeft.size() tRight))){vLeft.pop_back();}iRet min(iRet, tRight - (int)vLeft.size());sRight--;} return iRet;}int m_c;
};2023年3月旧代码
class Solution { public: int minimumScore(string s, string t) { m_c t.length(); m_c2 s.length(); m_vLeft.assign(m_c, m_c2); m_vRight.assign(m_c, -1); { int j 0; for (int i 0; i m_c; i) { while ((j m_c2) (s[j] ! t[i])) { j; } if (s.length() j) { break; } m_vLeft[i] j; } } { int j s.length()-1 ; for (int i m_c - 1; i 0; i–) { while ((j 0 ) (s[j] ! t[i])) { j–; } if (-1 j) { break; } m_vRight[i] j–; } } int left -1, right m_c; for (; left 1 ! right;) { const int len (left right) / 2; if (Can(len)) { right len; } else { left len; } } return right; } bool Can(int len) { for (int i 0; i len - 1 m_c; i) { bool bCan true; if (i len m_c) { bCan m_vLeft[i - 1] m_c2; } else if (0 i) { bCan m_vRight[i len] -1; } else { bCan m_vLeft[i - 1] m_vRight[i len]; } if (bCan) { return true; } } return false; } vector m_vLeft, m_vRight; int m_c; int m_c2; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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**实现。
