找马云做网站,自己做网站 怎么解决安全问题,齐三seo,万江做网站的公司作者推荐
视频算法专题
本文涉及知识点
动态规划汇总
LeetCode 1531. 压缩字符串 II
行程长度编码 是一种常用的字符串压缩方法#xff0c;它将连续的相同字符#xff08;重复 2 次或更多次#xff09;替换为字符和表示字符计数的数字#xff08;行程长度#xff09;…作者推荐
视频算法专题
本文涉及知识点
动态规划汇总
LeetCode 1531. 压缩字符串 II
行程长度编码 是一种常用的字符串压缩方法它将连续的相同字符重复 2 次或更多次替换为字符和表示字符计数的数字行程长度。例如用此方法压缩字符串 “aabccc” 将 “aa” 替换为 “a2” “ccc” 替换为 “c3” 。因此压缩后的字符串变为 “a2bc3” 。 注意本问题中压缩时没有在单个字符后附加计数 ‘1’ 。 给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符以使 s 的行程长度编码长度最小。 请你返回删除最多 k 个字符后s 行程长度编码的最小长度 。 示例 1 输入s “aaabcccd”, k 2 输出4 解释在不删除任何内容的情况下压缩后的字符串是 “a3bc3d” 长度为 6 。最优的方案是删除 ‘b’ 和 ‘d’这样一来压缩后的字符串为 “a3c3” 长度是 4 。 示例 2 输入s “aabbaa”, k 2 输出2 解释如果删去两个 ‘b’ 字符那么压缩后的字符串是长度为 2 的 “a4” 。 示例 3 输入s “aaaaaaaaaaa”, k 0 输出3 解释由于 k 等于 0 不能删去任何字符。压缩后的字符串是 “a11” 长度为 3 。 提示 1 s.length 100 0 k s.length s 仅包含小写英文字母
动态规划
预处理
将s转成arr每个元素是{字符长度}。 比如aabbaa变成{{‘a’,2},{b,2},{‘a’,2}} 长度0表示0个字符。长度1表示1个字符。长度2表示2到9.长度3表示10到99长度4表示100及以上。
动态规划的状态表示
pre[j] 表示处理完arr[0,i)后 用去j个字符的最短行程码。 dp[j] 表示处理完arr[0,i]后 用去j个字符的最短行程码。 pre2[ch][j][m] 表示处理完arr[0,i)后,以cha’结尾用去j个字符最后有m个ch的最短行程码。 dp2表示处理完arr[0,i]…
动态规划的转移方程
arr[i]没有和前面的元素合并 枚举j枚举减少长度0、1、2、3、4 arr[j]和前面的合并 枚举j,m 再枚举减少长度:0、1、2、3 、4 合并示例aa d d ‾ \underline{dd} ddaa 删除dd后就是4个aa了。
动态规划的初始状态
pre[0]0,其它100。 pre2全部100。
动态规划的填表顺序
i从小到大。
动态规划的返回值
pre.back().back()
代码
核心代码
class Solution {
public:int getLengthOfOptimalCompression(string s, int k) {const int lenArr s.length();vectorpairchar, int arr;for (int left 0, i 0; i s.length(); i){if ((i s.length()) || (s[left] ! s[i])){arr.emplace_back(s[left], i - left);left i;}}vectorint vLen { 0,1,2,10,100 };auto GetCodeLen [vLen](int len){int i vLen.size() - 1;for (; (i 0) (len vLen[i]); i--);return i;};auto MaxLen [vLen](int len){return vLen[len 1] - 1;};vectorint pre(lenArr 1, 100);pre[0] 0;vectorvectorvectorint dp3(26, vectorvectorint(lenArr1, vectorint(lenArr 1, 100)));for (const auto [ch, cnt] : arr){vectorint dp(lenArr 1, 100);auto dp2 dp3[ch - a];auto pre2 dp2;auto Update [lenArr,dp,dp2](int j, int iCodeLen,const char chEnd,int iEndLen){if (j lenArr){return;}dp[j] min(dp[j], iCodeLen);if (iEndLen lenArr){dp2[j][iEndLen] min(dp2[j][iEndLen], iCodeLen);}}; //处理没合并for (int j 0; j lenArr; j){ const int curCodeLen GetCodeLen(cnt);Update(j cnt, pre[j] curCodeLen,ch,cnt);for (int curCodeLen2 curCodeLen - 1; curCodeLen2 0; curCodeLen2--){//处理 行程妈缩短1,2...Update(j MaxLen(curCodeLen2), pre[j] curCodeLen2,ch, MaxLen(curCodeLen2));}}for (int j 0; j lenArr; j){for (int m 0; m j; m){const int curCodeLen GetCodeLen(cntm );Update(j cnt, pre2[j][m] - GetCodeLen(m) GetCodeLen(m cnt), ch, m cnt);for (int curCodeLen2 curCodeLen - 1; curCodeLen2 0; curCodeLen2--){//处理 行程妈缩短1,2...Update(j -m MaxLen(curCodeLen2), pre2[j][m] - GetCodeLen(m) curCodeLen2,ch, MaxLen(curCodeLen2));}}}pre.swap(dp); }return *std::min_element(pre.begin() pre.size() - k-1, pre.end());}
};测试用例
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;int k;{Solution sln;s aaa, k 2;auto res sln.getLengthOfOptimalCompression(s, k);Assert(1, res);}{Solution sln;s aaab, k 2;auto res sln.getLengthOfOptimalCompression(s, k);Assert(2, res);}{Solution sln;s aaabcccd, k 2;auto res sln.getLengthOfOptimalCompression(s, k);Assert(4, res);}{Solution sln;s aabbaa, k 2;auto res sln.getLengthOfOptimalCompression(s, k);Assert(2, res);}{Solution sln;s aaaaaaaaaaa, k 0;auto res sln.getLengthOfOptimalCompression(s, k);Assert(3, res);}{Solution sln;s spnskpulpsiqagreoajsltdrdlnpsdqapmsdlnlirasgfijafeoqjnddpaifsqpghshclqummgootsmkcgneofrkboirkplqijoi, k 25;auto res sln.getLengthOfOptimalCompression(s, k);Assert(3, res);}}动态规划优化
前一个解法的空间复杂度在过与不过的边缘。
动态规划的状态表示
dp[i][j] 表示处理了arr[0,i)选择了j个字符的最短行程码。
动态规划的转移方程
分两种情况 和前面的项目合并和前面的项不合并。细节同上。
动态规划的初始值
dp[0][0]0其它100。
动态规划的填表顺序
i从小到大j从小到大。
动态规划的返回值
dp.back的后k1个元素的最小值。
优化后的代码
class Solution {
public:int getLengthOfOptimalCompression(string s, int k) {const int lenArr s.length();vectorpairchar, int arr;for (int left 0, i 0; i s.length(); i){if ((i s.length()) || (s[left] ! s[i])){arr.emplace_back(s[left], i - left);left i;}}vectorint vLen { 0,1,2,10,100 };auto GetCodeLen [vLen](int len){int i vLen.size() - 1;for (; (i 0) (len vLen[i]); i--);return i;};auto MaxLen [vLen](int len){return vLen[len 1] - 1;};vectorvectorint dp(arr.size() 1, vectorint(lenArr 1, 100));dp[0][0] 0;int i -1;for (const auto [ch, cnt] : arr){i;auto pre dp[i];auto cur dp[i 1];auto Update [lenArr, cur](int j, int iCodeLen){if (j lenArr){return;}cur[j] min(cur[j], iCodeLen);};//处理没合并for (int j 0; j lenArr; j){const int curCodeLen GetCodeLen(cnt);Update(j cnt, pre[j] curCodeLen);for (int curCodeLen2 curCodeLen - 1; curCodeLen2 0; curCodeLen2--){//处理 行程妈缩短1,2...Update(j MaxLen(curCodeLen2), pre[j] curCodeLen2);}}int cnt2 0;for (int m i ; m 0; m--){if (arr[m].first ! ch){continue;}cnt2 arr[m].second;//合并后的字符数 const int curCodeLen GetCodeLen(cnt2);for (int j 0; j lenArr; j){Update(j cnt2, dp[m][j] curCodeLen);for (int curCodeLen2 curCodeLen - 1; curCodeLen2 0; curCodeLen2--){//处理 行程妈缩短1,2...Update(j MaxLen(curCodeLen2), dp[m][j] curCodeLen2);}}} }return *std::min_element(dp.back().begin() dp.back().size() - k - 1, dp.back().end());}
};动态规划三
arr数组少许提升性能但增加了复杂度不采用。
动态规划的状态
dp[i][j]表示 从s[0,i)中删除j个字符 最短的行程码。
动态规划的转移方程
令x dp[i1][j] 情况一删除s[i1] 那x等于dp[i][j-1] 公式一 情况二不删除且可能和前面的字符结合后删除。 不市一般性令s[i]‘a’且它的前面只有三个’a’小标分别为i1,i2,i3。 情况a s[i]没有和其它’a’结合则x dp[i][j]GetCodeLen (1)。 公式二 情况b: s[i]和s[i3]结合s(i3,i)之间非’a’的数量为diff全部删除。 b1: i和i3 都没删除。 x dp[i3][j-diff] GetCodeLen(2) → \rightarrow → dp[i-diff-1][j-diff] GetCodeLen(2) 公式三 b2: i3删除。x dp[i3][j-diff-1] GetCodeLen(1) → \rightarrow → dp[i-diff-1][j-diff-1] GetCodeLen(1) 就是公式二和公式一结合。 情况c: s[i]和s[i2] s[i3]结合 s(i2,i)之间非’a’的数量为diff2全部删除。 c1不删除’a’。 dp[i2][j-diff2] GetCodeLen(3) ** 公式四** c2删除一个’a’ dp[i2][j-diff2-1] GetCodeLen(2) → \rightarrow → dp[i-diff2-2][j-diff2-1]GetCodeLen(2) 就是公式三和公式的结合不需要枚举。 c3 删除两个’a’。dp[i-diff2-2][j-diff2-2] GetCodeLen(1) 就是公式二和公式一结合不用枚举。 总结: 无论多少个字符结合全删除就是公式一。 保留一个就是公式二。 保留三个就是公式三。 … m个字符结合只需要枚举m个字符,mm个字符(mm m )枚举mm个字符结合的时候考虑。
可以这样理解 m个字符合并后删除m-mm个保留mm个。 保留任意mm个都一样那保留后mm个。所以只需要枚举保留后mm个。
动态规划的初始值
dp[0][0] 0其它100。
动态规划的填表顺序
i从小到大。
动态规划的返回值
dp.back()的最小值。
代码
class Solution {
public:int getLengthOfOptimalCompression(string s, int k) {const int n s.length(); vectorint vLen { 0,1,2,10,100 };auto GetCodeLen [vLen](int len){int i vLen.size() - 1;for (; (i 0) (len vLen[i]); i--);return i;};vectorvectorint dp(n 1, vectorint(k 1, 100));dp[0][0] 0;for (int i 0; i n; i){//处理删除s[i]for (int j1 1; j1 min(i1,k); j1){dp[i1][j1] dp[i][j1-1];}//处理不删除s[i]for (int same 0, diff 0, preLen i;preLen0; preLen--){if (s[preLen] s[i]){same;for (int j1 diff; j1 min(i 1, k); j1){dp[i 1][j1] min(dp[i 1][j1], dp[i 1 - same - diff][j1 - diff] GetCodeLen(same));} }else{diff;}}} return *std::min_element(dp.back().begin() , dp.back().end());}
};2023年2月 第一版
class Solution { public: int getLengthOfOptimalCompression(const string s, const int k) { int pre[100 1][27][101]; memset(pre, 101, sizeof(pre)); pre[0][26][1] 0; for (const auto ch : s) { int dp[100 1][27][101]; memset(dp, 101, sizeof(dp)); for (int iK 0; iK k; iK) { for (int j 0; j 27; j) { for (int iNew 0; iNew 101; iNew) { const int iLen pre[iK][j][iNew]; if (iLen 100) { continue; } if (iK k) {//删除 dp[iK 1][j][iNew] min(dp[iK 1][j][iNew], iLen); } if (j ‘a’ ! ch) { dp[iK][ch - ‘a’][1] min(dp[iK][ch - ‘a’][1], iLen 1); } else { const int iNewNum min(100, iNew 1); dp[iK][ch - ‘a’][iNewNum] min(dp[iK][ch - ‘a’][iNewNum], iLen ((1 iNew) || (9 iNew) || (99 iNew))); } } } } memcpy(pre,dp, sizeof(pre)); } int iMin INT_MAX; if (100 s.length()) { const char chMin *std::min_element(s.begin(), s.end()); const char chMax *std::max_element(s.begin(), s.end()); if (chMin chMax) { iMin 4; } } for (int iK 0; iK k; iK) { for (int j 0; j 27; j) { for (int iNew 0; iNew 101; iNew) { if (pre[iK][j][iNew] iMin) { iMin pre[iK][j][iNew]; } } } } return iMin; } };
2023年2月 第二版
class Solution { public: int getLengthOfOptimalCompression(const string s, const int k) { if (100 s.length()) { const char chMin *std::min_element(s.begin(), s.end()); const char chMax *std::max_element(s.begin(), s.end()); if (chMin chMax) { const int iRemain s.length() - k; if (iRemain 100) { return 4; } if (iRemain 10) { return 3; } if (iRemain 2 ) { return 2; } return iRemain; } } int pre[100 1][27][11]; memset(pre, 101, sizeof(pre)); pre[0][26][1] 0; for (const auto ch : s) { int dp[100 1][27][11]; memset(dp, 101, sizeof(dp)); for (int iK 0; iK k; iK) { for (int j 0; j 27; j) { for (int iNew 0; iNew 11; iNew) { const int iLen pre[iK][j][iNew]; if (iLen 100) { continue; } if (iK k) {//删除 dp[iK 1][j][iNew] min(dp[iK 1][j][iNew], iLen); } if (j ‘a’ ! ch) { dp[iK][ch - ‘a’][1] min(dp[iK][ch - ‘a’][1], iLen 1); } else { const int iNewNum min(10, iNew 1); dp[iK][ch - ‘a’][iNewNum] min(dp[iK][ch - ‘a’][iNewNum], iLen ((1 iNew) || (9 iNew) || (99 iNew))); } } } } memcpy(pre, dp, sizeof(pre)); } int iMin INT_MAX; for (int iK 0; iK k; iK) { for (int j 0; j 27; j) { for (int iNew 0; iNew 11; iNew) { if (pre[iK][j][iNew] iMin) { iMin pre[iK][j][iNew]; } } } } return iMin; } };
2023年2月版
class Solution { public: int getLengthOfOptimalCompression(const string s, const int k) { if (100 s.length()) { const char chMin *std::min_element(s.begin(), s.end()); const char chMax *std::max_element(s.begin(), s.end()); if (chMin chMax) { const int iRemain s.length() - k; if (iRemain 100) { return 4; } if (iRemain 10) { return 3; } if (iRemain 2 ) { return 2; } return iRemain; } } int pre[100 1][27][11]; memset(pre, 101, sizeof(pre)); pre[0][26][1] 0; for (const auto ch : s) { int dp[100 1][27][11]; memset(dp, 101, sizeof(dp)); for (int iK 0; iK k; iK) { for (int j 0; j 27; j) { for (int iNew 1; iNew 11; iNew) { const int iLen pre[iK][j][iNew]; if (iLen 100) { continue; } if (iK k) {//删除 dp[iK 1][j][iNew] min(dp[iK 1][j][iNew], iLen); } if (j ‘a’ ! ch) { dp[iK][ch - ‘a’][1] min(dp[iK][ch - ‘a’][1], iLen 1); } else { const int iNewNum min(10, iNew 1); dp[iK][ch - ‘a’][iNewNum] min(dp[iK][ch - ‘a’][iNewNum], iLen ((1 iNew) || (9 iNew) || (99 iNew))); } } } } memcpy(pre, dp, sizeof(pre)); } int iMin INT_MAX; for (int iK 0; iK k; iK) { for (int j 0; j 27; j) { for (int iNew 1; iNew 11; iNew) { if (pre[iK][j][iNew] iMin) { iMin pre[iK][j][iNew]; } } } } return iMin; } };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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**实现。
