作者推荐
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
本题其它解法
题目
给你一个字符串 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_aCharNums | iWindowWidth个字符，各字母的数量 |
代码
核心代码
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)&&((iWindowWidth=m_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)&&((iWindowWidth=m_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; };
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
