教做网站,决定网站打开的速度吗,网站建设公司网站建设公司,外贸自建站平台价格作者推荐
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
本题其它解法
【离散差分】LeetCode2953:统计完全子字符串
题目
给你一个字符串 word 和一个整数 k 。 如果 word 的一个子字符串 s 满足以下条件#xff0c;我们称它是 完全字符串#xff1a; s 中每个字符…作者推荐
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
本题其它解法
【离散差分】LeetCode2953:统计完全子字符串
题目
给你一个字符串 word 和一个整数 k 。 如果 word 的一个子字符串 s 满足以下条件我们称它是 完全字符串 s 中每个字符 恰好 出现 k 次。 相邻字符在字母表中的顺序 至多 相差 2 。也就是说s 中两个相邻字符 c1 和 c2 它们在字母表中的位置相差 至多 为 2 。 请你返回 word 中 完全 子字符串的数目。 子字符串 指的是一个字符串中一段连续 非空 的字符序列。 示例 1 输入word “igigee”, k 2 输出3 解释完全子字符串需要满足每个字符恰好出现 2 次且相邻字符相差至多为 2 igigee, igigee, igigee 。 示例 2 输入word “aaabbbccc”, k 3 输出6 解释完全子字符串需要满足每个字符恰好出现 3 次且相邻字符相差至多为 2 aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc 。 参数范围 1 word.length 105 word 只包含小写英文字母。 1 k word.length
滑动窗口
周赛的时候忽略了完全子字符串的长度是k的1到26倍。
时间复杂度
O(nmm)。n是字符串的长度m的字符种类也就是26。枚举字符结尾O(n)枚举窗口长度:O(m);统计合法字符数量O(m)。
变量解析
m_aCharNumsiWindowWidth个字符各字母的数量
代码
核心代码
class Solution { public: int countCompleteSubstrings(string word, int k) { m_iK k; int pre 0; int iRet 0; for (int i 0; i word.length(); i) { if (i (abs(word[i] - word[i - 1]) 2)) { iRet Do(word.data()pre, i - pre); pre i; } } iRet Do(word.data() pre, word.length() - pre); return iRet; } int Do(const char* p ,int len) { int iRet 0; auto AddNum { for (int i 0; i 26; i) { if ((0 ! m_aCharNums[i]) (m_iK ! m_aCharNums[i])) { return; } } iRet; }; int iWindowWidth 0; for (int i 1; (i 26)((iWindowWidthm_iK*i) len); i) { memset(m_aCharNums, 0, sizeof(m_aCharNums)); int j 0; for (; j iWindowWidth; j) { m_aCharNums[p[j] - ‘a’]; } AddNum(); for (;j len; j) { m_aCharNums[p[j] - ‘a’]; m_aCharNums[p[j - iWindowWidth] - ‘a’]–; AddNum(); } } return iRet; } int m_aCharNums[26]; int m_iK; };
测试用例
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; int k, res; { Solution slu; s “ba”; k 1; auto res slu.countCompleteSubstrings(s, k); Assert(3, res); } { Solution slu; s “gvgvvgv”; k 2; auto res slu.countCompleteSubstrings(s, k); Assert(1, res); } { Solution slu; s “igigee”; k 2; auto res slu.countCompleteSubstrings(s, k); Assert(3, res); } { Solution slu; s “aaabbbccc”; k 3; auto res slu.countCompleteSubstrings(s, k); Assert(6, res); }
//CConsole::Out(res);}
优化
不用每次都判断无法字符的数量只会修改两个字符的数量只判断这两个字符就可以了。
时间复杂度
O(nm)。
代码
class Solution {
public:int countCompleteSubstrings(string word, int k) {m_iK k;int pre 0;int iRet 0;for (int i 0; i word.length(); i){if (i (abs(word[i] - word[i - 1]) 2)){iRet Do(word.data()pre, i - pre);pre i;}}iRet Do(word.data() pre, word.length() - pre);return iRet;}int Do(const char* p ,int len){int iRet 0; int iWindowWidth 0;for (int i 1; (i 26)((iWindowWidthm_iK*i) len); i){memset(m_aCharNums, 0, sizeof(m_aCharNums));int j 0;for (; j iWindowWidth; j){m_aCharNums[p[j] - a];}int iVilidCount std::count(m_aCharNums, m_aCharNums 26, 0) std::count(m_aCharNums, m_aCharNums 26, m_iK);if (26 iVilidCount){iRet;}auto Change [](int index, int iAdd){bool bOld (0 m_aCharNums[index]) || (m_iK m_aCharNums[index]);m_aCharNums[index] iAdd;bool bNew (0 m_aCharNums[index]) || (m_iK m_aCharNums[index]);iVilidCount (int)bNew - (int)bOld;};for (;j len; j){Change(p[j] - a,1);Change(p[j - iWindowWidth] - a, -1);iRet (26 iVilidCount);}}return iRet;}int m_aCharNums[26];int m_iK;
};扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
