泉州市服务好的网站设计,电子商务网站开发课程设计论文,网站建设怎么付费,北京seo顾问外包本文涉及的基础知识点
动态规划
题目
得到 K 个半回文串的最少修改次数 给你一个字符串 s 和一个整数 k #xff0c;请你将 s 分成 k 个 子字符串 #xff0c;使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。 请你返回一个整数#xff0c;表示需要修改的 最少…本文涉及的基础知识点
动态规划
题目
得到 K 个半回文串的最少修改次数 给你一个字符串 s 和一个整数 k 请你将 s 分成 k 个 子字符串 使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。 请你返回一个整数表示需要修改的 最少 字符数目。 注意 如果一个字符串从左往右和从右往左读是一样的那么它是一个 回文串 。 如果长度为 len 的字符串存在一个满足 1 d len 的正整数 d len % d 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 那么我们说这个字符串是 半回文串 。比方说 “aa” “aba” “adbgad” 和 “abab” 都是 半回文串 而 “a” “ab” 和 “abca” 不是。 子字符串 指的是一个字符串中一段连续的字符序列。 示例 1 输入s “abcac”, k 2 输出1 解释我们可以将 s 分成子字符串 “ab” 和 “cac” 。子字符串 “cac” 已经是半回文串。如果我们将 “ab” 变成 “aa” 它也会变成一个 d 1 的半回文串。 该方案是将 s 分成 2 个子字符串的前提下得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。 示例 2: 输入s “abcdef”, k 2 输出2 解释我们可以将 s 分成子字符串 “abc” 和 “def” 。子字符串 “abc” 和 “def” 都需要修改一个字符得到半回文串所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。 该方案是将 s 分成 2 个子字符串的前提下得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。 示例 3 输入s “aabbaa”, k 3 输出0 解释我们可以将 s 分成子字符串 “aa” “bb” 和 “aa” 。 字符串 “aa” 和 “bb” 都已经是半回文串了。所以答案为 0 。 参数范围 2 s.length 200 1 k s.length / 2 s 只包含小写英文字母。
分析
第一轮vectorvector m_aDCenger[2][101]; 四维数组第一维,0表示奇数长度1表示偶数长度。 第二维d。第三维中心。第四维半长长度。值记录变成半回文需要改变的次数。 第二轮int m_vNeedNum[200][201] 记录s[left,r)变成半回文需要改变的次数。 第三轮三层循环第一层循环枚举k第二层循环枚举s[0,j]。第三轮循环枚举m[0,m]和(m,j]。 三轮时间复杂度都是O(nnn);
核心代码
class Solution { public: int minimumChanges(string s, int k) { m_c s.length(); Init(s); Init2(s); vector pre(m_c);//pre[j]将s[0,j]拆分成i-1个子字符串这些子串全部半回文的需要改变的字符数 for (int j 0; j m_c; j) { pre[j] m_vNeedNum[0][j 1]; } for (int i 2; i k; i) { vector dp(m_c); for (int j i - 1; j m_c; j) {//拆分成[0,m]和(m,j]([m1,j1))前者i-1个子串后者一个子串 int iMin INT_MAX; for (int m max(0,i-2); m j; m) { const int cur pre[m] m_vNeedNum[m 1][j 1]; iMin min(iMin, cur); } dp[j] iMin; } pre.swap(dp); } return pre.back(); } void Init(std::string s) { for(int i 0 ; i 2 ; i ) for (int j 0; j m_c / 2; j) { m_aDCenger[i][j].assign(m_c1, vector((m_c1)/21)); } for (int d 1; d m_c/2; d) { for (int center 0; center m_c; center) { int halfLen 1; while ((center d* (halfLen-1) m_c) (center - d* (halfLen - 1) 0) ) { m_aDCenger[1][d][center][halfLen] m_aDCenger[1][d][center][halfLen - 1] (s[center d * (halfLen - 1)] ! s[center - d * (halfLen - 1)]) ; halfLen; } } for (int center 0; center m_c; center) {//偶数半回文 int halfLen 1; while ((center d * halfLen m_c) (center - d * (halfLen - 1) 0) ) { m_aDCenger[0][d][center][halfLen] m_aDCenger[0][d][center][halfLen - 1] (s[center d * halfLen] ! s[center - d * (halfLen - 1)]); halfLen; } } } } void Init2(std::string s) { memset(m_vNeedNum, sizeof(m_vNeedNum), 0); for (int left 0; left m_c; left) { for (int r left 1; r m_c; r) { const int subLen r - left; int iNeed 1000*1000; for (int d 1; (d * d subLen)(subLen 1); d) { if (0 ! subLen % d) { continue; } { const int iCurNeed DoLeftRightD(left, r, d); iNeed min(iNeed, iCurNeed); } if(d 1 ) { const int iCurNeed DoLeftRightD(left, r, subLen/d); iNeed min(iNeed, iCurNeed); } } m_vNeedNum[left][r] iNeed; } } } int DoLeftRightD(int left,int r,int d) { const int subLen r - left; const int len subLen / d; const auto arr m_aDCenger[len % 2]; const int midIndex (len-1)/2; int iCurNeed 0; for (int begin 0; begin d; begin) { const int center left begin midIndex * d; iCurNeed arr[d][center][(len 1) / 2]; } return iCurNeed; } int m_c; vectorvector m_aDCenger[2][101]; int m_vNeedNum[200][201]; };
测试用例
template void Assert(const vector v1, const vector v2) { if (v1.size() ! v2.size()) { assert(false); return; } for (int i 0; i v1.size(); i) { assert(v1[i] v2[i]); } }
template void Assert(const T t1, const T t2) { assert(t1 t2); }
int main() { //string s “bbacccbbaabbddddddddddddddddddddddddddddddddddddddddddddbbacccbbaabbdddddddddddddddddddddddddddddddddddddddddddddbbbacccbbaabbddddddddddddddddddddbbacccbbaabbdddddddddddddddddddddddddddddddddddddddddd”; string s “abcac”; int k 2; Solution slu; auto res slu.minimumChanges(s,k); Assert(1, res);
//CConsole::Out(res);}
小幅改进
空间复杂度降为O(nn)。一预处理的时候利用当前d更新m_vLeftRightToNeedChange。更新完旧d的信息就不需要了。二不需要分奇数长度和偶数长度回文。长度本身可以分奇偶了。 Init2共3层循环时间复杂度是O(nn)第三层第四层时间复杂度共O(n)。第三层循环的时间复杂度是: n/d第四层时间复杂度是d。
新代码
class Solution {
public:int minimumChanges(string s, int k) {m_c s.length(); m_vLeftRightToNeedChange.assign(m_c, vectorint(m_c, m_iNotMay));for (int d 1; d m_c / 2; d){Init(s,d);Init2(s,d);}vectorint pre(m_c);//pre[j]将s[0,j]拆分成i-1个子字符串这些子串全部半回文的需要改变的字符数for (int j 0; j m_c; j){pre[j] m_vLeftRightToNeedChange[0][j];}for (int i 2; i k; i){vectorint dp(m_c);for (int j i - 1; j m_c; j){//拆分成[0,m]和(m,j]([m1,j]))前者i-1个子串后者一个子串int iMin INT_MAX;for (int m max(0,i-2); m j; m){const int cur pre[m] m_vLeftRightToNeedChange[m 1][j];iMin min(iMin, cur);}dp[j] iMin;}pre.swap(dp);}return pre.back();}void DoCenter(int center, bool bEven,int d,const string s){int left center, r left d*bEven;if (r m_c){return;}m_vDLeftRightToNeedChange[left][r] (s[left] ! s[r]);left - d;r d;while ((r m_c) (left 0 )){m_vDLeftRightToNeedChange[left][r] m_vDLeftRightToNeedChange[left d][r - d] (s[left] ! s[r]);left - d;r d;}}void Init(std::string s,int d ){m_vDLeftRightToNeedChange.assign(m_c, vectorint(m_c, m_iNotMay)); for (int center 0; center m_c; center){DoCenter(center, true, d,s);DoCenter(center, false, d,s);}}void Init2(std::string s, int d){ for (int left 0; left m_c; left){for (int iSubLen 2; left iSubLen*d m_c ; iSubLen){const int r left iSubLen * d;int iNeedChange 0;for (int j 0; j d; j){iNeedChange m_vDLeftRightToNeedChange[leftj][r - dj];}m_vLeftRightToNeedChange[left][r - 1] min(m_vLeftRightToNeedChange[left][r - 1],iNeedChange);}}} const int m_iNotMay 1000 * 1000;int m_c;vectorvectorint m_vDLeftRightToNeedChange;//m_vDLeftRightToNeedChange[left][r]表示当前d,str[left,leftd....r]是回文的最少次数vectorvectorint m_vLeftRightToNeedChange;//m_vLeftRightToNeedChange[left][r]表示s[leftr]变成半回文的最少改变次数
};扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
文章转载自： http://www.morning.huayaosteel.cn.gov.cn.huayaosteel.cn http://www.morning.xnkb.cn.gov.cn.xnkb.cn http://www.morning.hlwzd.cn.gov.cn.hlwzd.cn http://www.morning.pbbzn.cn.gov.cn.pbbzn.cn http://www.morning.splcc.cn.gov.cn.splcc.cn http://www.morning.yrxcn.cn.gov.cn.yrxcn.cn http://www.morning.rrrrsr.com.gov.cn.rrrrsr.com http://www.morning.rhmt.cn.gov.cn.rhmt.cn http://www.morning.nppml.cn.gov.cn.nppml.cn http://www.morning.wwsgl.com.gov.cn.wwsgl.com http://www.morning.kdnbf.cn.gov.cn.kdnbf.cn http://www.morning.clhyj.cn.gov.cn.clhyj.cn http://www.morning.wbfg.cn.gov.cn.wbfg.cn http://www.morning.qngcq.cn.gov.cn.qngcq.cn http://www.morning.hxcuvg.cn.gov.cn.hxcuvg.cn http://www.morning.gbyng.cn.gov.cn.gbyng.cn http://www.morning.bncrx.cn.gov.cn.bncrx.cn http://www.morning.rmqmc.cn.gov.cn.rmqmc.cn http://www.morning.sqlh.cn.gov.cn.sqlh.cn http://www.morning.kxnjg.cn.gov.cn.kxnjg.cn http://www.morning.qscsy.cn.gov.cn.qscsy.cn http://www.morning.jgykx.cn.gov.cn.jgykx.cn http://www.morning.yknsr.cn.gov.cn.yknsr.cn http://www.morning.zpzys.cn.gov.cn.zpzys.cn http://www.morning.bfwk.cn.gov.cn.bfwk.cn http://www.morning.bkwd.cn.gov.cn.bkwd.cn http://www.morning.jtjmz.cn.gov.cn.jtjmz.cn http://www.morning.lddpj.cn.gov.cn.lddpj.cn http://www.morning.mnjwj.cn.gov.cn.mnjwj.cn http://www.morning.lzqxb.cn.gov.cn.lzqxb.cn http://www.morning.xpqsk.cn.gov.cn.xpqsk.cn http://www.morning.hxwhyjh.com.gov.cn.hxwhyjh.com http://www.morning.lhyhx.cn.gov.cn.lhyhx.cn http://www.morning.skrh.cn.gov.cn.skrh.cn http://www.morning.xkjrs.cn.gov.cn.xkjrs.cn http://www.morning.knqzd.cn.gov.cn.knqzd.cn http://www.morning.xxsrm.cn.gov.cn.xxsrm.cn http://www.morning.tmbtm.cn.gov.cn.tmbtm.cn http://www.morning.pkmw.cn.gov.cn.pkmw.cn http://www.morning.tqsmc.cn.gov.cn.tqsmc.cn http://www.morning.smj78.cn.gov.cn.smj78.cn http://www.morning.qfbzj.cn.gov.cn.qfbzj.cn http://www.morning.rdsst.cn.gov.cn.rdsst.cn http://www.morning.jrhcp.cn.gov.cn.jrhcp.cn http://www.morning.npbnc.cn.gov.cn.npbnc.cn http://www.morning.tpssx.cn.gov.cn.tpssx.cn http://www.morning.xhkgl.cn.gov.cn.xhkgl.cn http://www.morning.knrgb.cn.gov.cn.knrgb.cn http://www.morning.gghhmi.cn.gov.cn.gghhmi.cn http://www.morning.gnlyq.cn.gov.cn.gnlyq.cn http://www.morning.czgtt.cn.gov.cn.czgtt.cn http://www.morning.hhrpy.cn.gov.cn.hhrpy.cn http://www.morning.lxhny.cn.gov.cn.lxhny.cn http://www.morning.lffrh.cn.gov.cn.lffrh.cn http://www.morning.rkjz.cn.gov.cn.rkjz.cn http://www.morning.baohum.com.gov.cn.baohum.com http://www.morning.yfddl.cn.gov.cn.yfddl.cn http://www.morning.jgzmr.cn.gov.cn.jgzmr.cn http://www.morning.xjtnp.cn.gov.cn.xjtnp.cn http://www.morning.nmkfy.cn.gov.cn.nmkfy.cn http://www.morning.fwkjp.cn.gov.cn.fwkjp.cn http://www.morning.qmnhw.cn.gov.cn.qmnhw.cn http://www.morning.wjplm.cn.gov.cn.wjplm.cn http://www.morning.wztlr.cn.gov.cn.wztlr.cn http://www.morning.cbynh.cn.gov.cn.cbynh.cn http://www.morning.xsfg.cn.gov.cn.xsfg.cn http://www.morning.wqhlj.cn.gov.cn.wqhlj.cn http://www.morning.fmkjx.cn.gov.cn.fmkjx.cn http://www.morning.ygztf.cn.gov.cn.ygztf.cn http://www.morning.qcymf.cn.gov.cn.qcymf.cn http://www.morning.mlnbd.cn.gov.cn.mlnbd.cn http://www.morning.whothehellami.com.gov.cn.whothehellami.com http://www.morning.rxfbf.cn.gov.cn.rxfbf.cn http://www.morning.wrkcw.cn.gov.cn.wrkcw.cn http://www.morning.hwnnh.cn.gov.cn.hwnnh.cn http://www.morning.lbbyx.cn.gov.cn.lbbyx.cn http://www.morning.grlth.cn.gov.cn.grlth.cn http://www.morning.ydryk.cn.gov.cn.ydryk.cn http://www.morning.c7513.cn.gov.cn.c7513.cn http://www.morning.qgmwt.cn.gov.cn.qgmwt.cn
