上海网站建设咨询站霸网络,做网站app需多少钱,微信表情制作小程序,wordpress 图像相册本文涉及知识点
贪心 回溯 字符串
LeetCode2014. 重复 K 次的最长子序列
给你一个长度为 n 的字符串 s #xff0c;和一个整数 k 。请你找出字符串 s 中 重复 k 次的 最长子序列 。 子序列 是由其他字符串删除某些#xff08;或不删除#xff09;字符派生而来的一个字符串…本文涉及知识点
贪心 回溯 字符串
LeetCode2014. 重复 K 次的最长子序列
给你一个长度为 n 的字符串 s 和一个整数 k 。请你找出字符串 s 中 重复 k 次的 最长子序列 。 子序列 是由其他字符串删除某些或不删除字符派生而来的一个字符串。 如果 seq * k 是 s 的一个子序列其中 seq * k 表示一个由 seq 串联 k 次构造的字符串那么就称 seq 是字符串 s 中一个 重复 k 次 的子序列。 举个例子“bba” 是字符串 “bababcba” 中的一个重复 2 次的子序列因为字符串 “bbabba” 是由 “bba” 串联 2 次构造的而 “bbabba” 是字符串 “bababcba” 的一个子序列。 返回字符串 s 中 重复 k 次的最长子序列 。如果存在多个满足的子序列则返回 字典序最大 的那个。如果不存在这样的子序列返回一个 空 字符串。 示例 1 example 1 输入s “letsleetcode”, k 2 输出“let” 解释存在两个最长子序列重复 2 次let 和 “ete” 。 “let” 是其中字典序最大的一个。 示例 2 输入s “bb”, k 2 输出“b” 解释重复 2 次的最长子序列是 “b” 。 示例 3 输入s “ab”, k 2 输出“” 解释不存在重复 2 次的最长子序列。返回空字符串。
提示 n s.length 2 k 2000 2 n k * 8 s 由小写英文字母组成
回溯
因为n k*8 则最多7个字符。 string s1 记录 出现数量k次的字符。如果一个字符出现m × \times ×k次则记录m次。 枚举mask ∈ \in ∈ [1,1 s1.length()]。 for(int i 0 ; i s1.length();i ) { if(mask(1i)) { s2 s1[i]; } } 将s2 降序排序计算是否存在k个为s2的子序列。如果有直接返回否则用系统函数prev_permutation计算前一个字典序。
代码
核心代码
class Solution {
public:string longestSubsequenceRepeatedK(string s, int k) {m_s s;m_iK k;int cnt[26] { 0 };for (const auto ch : s){cnt[ch - a];}string s1;for (int i 0; i 26; i){s1 string(cnt[i] / k, a i);}const int n s1.length();for (int i 1; i (1 n); i){string s2;for (int j 0; j n; j){if (i (1 j)){s2 s1[j];}}Do(s2);}return m_res.empty() ? : m_res.rbegin()-second;}void Do(string s2){sort(s2.begin(), s2.end(), std::greater());do{int cnt 0;for (const auto ch : m_s){if (ch s2[cnt % s2.length()]){cnt;}}if (cnt m_iK * s2.length()){m_res.emplace(s2.length(), s2);if (m_res.size() 1){m_res.erase(m_res.begin());}}} while (prev_permutation(s2.begin(), s2.end()));}setpairint, string m_res;string m_s;int m_iK;
};2023年5月版
class Solution { public: string longestSubsequenceRepeatedK(string s, int k) { m_s s; m_c s.length(); m_iK k; m_vFreq.resize(26); for (const charch : s) { m_vFreq[ch - ‘a’]; } for (int len 7; len 0; len–) { string str dfs(“”, len); if (str.length()) { return str; } } return “”; } string dfs(string str,int leve) { if (0 leve) { return Do(str)?str:“”; } for (int i 25; i 0; i–) { if (m_vFreq[i] m_iK) { continue; } m_vFreq[i] - m_iK; string strRet dfs(str char(i ‘a’), leve - 1); if (strRet.length()) { return strRet; } m_vFreq[i] m_iK; } return “”; } bool Do(const string strSub) { int iSBegin 0; int i 0, k 0; for (; iSBegin m_c; iSBegin) { if (strSub[i] m_s[iSBegin]) { i; } if (strSub.length() i) { i 0; k; } if (m_iK k) { return true; } } return false; } int m_c; string m_s; int m_iK; vector m_vFreq; };
2023年7月
class Solution { public: string longestSubsequenceRepeatedK(string s, int k) { m_c s.length(); m_iK k; m_s s; m_vNums.assign(m_c1, vector(26)); /* for (int i m_c - 1; i 0; i–) { m_vNums[i] m_vNums[i 1]; m_vNums[i][s[i] - ‘a’]; } / for (int i 0; i m_c; i) { m_vIndexs[s[i] - ‘a’].emplace_back(i); } vector cur; int aUse[26] { 0 }; dfs(cur, aUse, 0); return m_strRet; } void dfs(vector cur,int aUse, int iCurIndex) { for (int i 0; i 26; i) { const auto v m_vIndexs[i]; int index std::lower_bound(v.begin(), v.end(), iCurIndex) - v.begin(); if (index v.size()) { continue; } cur.push_back(i); aUse[i]; if (Check(cur, aUse, v[index] 1)) { dfs(cur, aUse, v[index] 1); } cur.pop_back(); aUse[i]–; } } bool Check(const vector cur, int* aUse, int iCurIndex) { for (int i 1; i m_iK; i) { for (const auto ch : cur) { const auto v m_vIndexs[ch]; int index std::lower_bound(v.begin(), v.end(), iCurIndex) - v.begin(); if (index v.size()) { return false; } iCurIndex v[index] 1; } } string ret; for (const auto tmp : cur) { ret ‘a’ tmp; } if (ret.length() m_strRet.length()) { m_strRet ret; } else if (ret.length() m_strRet.length()) { if (ret m_strRet) { m_strRet ret; } } return true; } int m_c; vectorvector m_vNums; std::vector m_vIndexs[26]; int m_iK; string m_s; string m_strRet; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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**实现。
