打开网站显示建设中,枣阳网站开发,wordpress搭建群空间,时事新闻热点摘抄作者推荐
视频算法专题
本文涉及知识点
字符串 字典序 分类讨论 本题无法使用KMP#xff0c;因为t1不段变化。
LeetCode1163. 按字典序排在最后的子串
给你一个字符串 s #xff0c;找出它的所有子串并按字典序排列#xff0c;返回排在最后的那个子串。 示例 1#xf…作者推荐
视频算法专题
本文涉及知识点
字符串 字典序 分类讨论 本题无法使用KMP因为t1不段变化。
LeetCode1163. 按字典序排在最后的子串
给你一个字符串 s 找出它的所有子串并按字典序排列返回排在最后的那个子串。 示例 1 输入s “abab” 输出“bab” 解释我们可以找出 7 个子串 [“a”, “ab”, “aba”, “abab”, “b”, “ba”, “bab”]。按字典序排在最后的子串是 “bab”。 示例 2 输入s “leetcode” 输出“tcode” 提示 1 s.length 4 * 105 s 仅含有小写英文字符。
KMP
令s[0,i)的最后子串是t1s[0,i]的最后子串t2。则t2一定以s[i]结尾因为t1s[i]一定在t1后面。 { 从 t 1 取 0 个字符 t 2 s [ i ] s [ i ] t [ 0 ] 从 t 1 取后 m 个字符 t [ i − m , i ) s [ i ] 条件下面详述 \begin{cases} 从t1取0个字符t2 s[i] s[i] t[0] \\ 从t1取后m个字符 t[i-m,i)s[i] 条件下面详述\\ \end{cases} {从t1取0个字符t2s[i]从t1取后m个字符t[i−m,i)s[i]s[i]t[0]条件下面详述 t1[0,m) 不会小于 t[i-m,i)否则t1就是t[n-m,m)。 如果两种是大于关系则t1[0,m]大于 t[i-m,i)s[i] ,不成立。 故一定是相等关系且t1[m]小于s[i]。 可以利用KMP的公共前后缀。 如果以上情况都不符合则t2 t1 s[i]。 如果使用KMP,t1不断变化时间复杂度是O(nn)超时。
分类讨论
令n s.length()。 性质一令s[x,y)是最后的子串x ∈ \in ∈[0,n)则yn。因为s[x,n)的字典序比s[x,y)大。 性质二:令s[i,n)在s[x,n)中的字典序最大x ∈ \in ∈[0,j)。确保:j i。 令s[i,ik)和s[j,jk)相等,下标 jK非法 s[ik]!s[jk]。初始i0,j1,k0 { k s [ i k ] s [ j k ] k 0 , i j , j s [ i k ] s [ j k ] 待证明一 k 0 , i k 1 s [ i k ] s [ j k ] 待证明二 \begin{cases} k s[ik]s[jk] \\ k0,ij,j s[ik] s[jk] 待证明一\\ k0,i k1 s[ik] s[jk] 待证明二\\ \end{cases} ⎩ ⎨ ⎧kk0,ij,jk0,ik1s[ik]s[jk]s[ik]s[jk]s[ik]s[jk]待证明一待证明二
待证明一
显然s[j,n)的字典序大于s[i,n)结合性质二s[j,n)是 s[x,n)中的最大字典序x ∈ \in ∈[0,j1)。
待证明二
令x ∈ \in ∈[j,jk] 则len x - j1 。 s[x,n)的字典序小于s[ilen,n)结合性质二,s[ilen,n)小于s[i],s[x,n)小于s[i,n)。现在来证明无后效性 从小到处理len则: s[0,jlen)符合性质二由于s[0,ilen]符合性质二。
超时
多余n-1个a后面跟一个b。时间复杂度O(nn)。
代码
核心代码
class Solution {
public:string lastSubstring(string s) {int i 0;for (int j 1; j s.length(); ){int k 0;for (; ((j k) s.length()) (s[j k] s[i k]); k);int tmp i;if (s[i k] s[j k]){i j;}else{j k 1;} }return s.substr(i);}
};测试用例
templateclass T,class T2
void Assert(const T t1, const T2 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 cacacb;auto res sln.lastSubstring(s);Assert(cb, res);}{Solution sln;s abab;auto res sln.lastSubstring(s);Assert(bab, res);}{Solution sln;s leetcode;auto res sln.lastSubstring(s);Assert(tcode, res);}}优化
极端情况下ij执行了n次,k也为n。故时间复杂度为O(nn)。 分两种情况 一ik j 不变。 二ik j。下面具体分析 令m j-i。 将s[j,jk)和s[i,ik)分成若干块,最后一块长度为k%m,前面的块长度都为m则 s[j,jk)的各块分别为s[j,i) s[i,im) s[im,im2) ⋯ \cdots ⋯ s[i,ik)的个块分别为s[i,im) s[im,im2) ⋯ \cdots ⋯ → \rightarrow → s[j,i) s [i,im) s[im,im*2) ⋯ \cdots ⋯ 显然s[j,n)淘汰了s[i,n) x$\in[0,m) s[j,n)能够淘汰s[jn,n) 因为s[i,n)删除前m个字符s[ix,n)删除就是两者。 同理s[jm,n)能淘汰s[j]和s[jmx,n)。 ⋮ \vdots ⋮ 故 i j k - (k%m) ⟺ \iff ⟺ imk - (k%m) 因为 m k%m 所以 imk - (k%m) i k也就i至少增加k。 无论什么情况 i或j至少有一个至少增加k故总时间复杂度是O(n)。
代码
class Solution {
public:string lastSubstring(string s) {int i 0;for (int j 1; j s.length(); ){int k 0;for (; ((j k) s.length()) (s[j k] s[i k]); k);int tmp i;if (s[i k] s[j k]){const int m j - i;if (k m){i (j k - k%m);j i 1;}else{i j;}}else{j k 1;} }return s.substr(i);}
};2023年5月版
class Solution { public: string lastSubstring(string s) { int iMaxIndex 0; for (int i 1; i s.length(); i) { int k 0; for (; (i k s.length()) (s[i k] s[iMaxIndex k]); k) { } if ((i k s.length()) (s[i k] s[iMaxIndex k])) { auto tmp iMaxIndex; iMaxIndex i; i max(i,tmpk); } else { i i k ; } } return s.substr(iMaxIndex); } };
2024年2月版
class Solution { public: string lastSubstring(string s) { int i 0; for (int j 1; j s.length(); ) { int k 0; for (; ((j k) s.length()) (s[j k] s[i k]); k); int tmp i; if (s[i k] s[j k]) { const int m j - i; if (k m) { i k1; j i 1; } else { i j; } } else { j k 1; } } return s.substr(i); } }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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**实现。
