作者推荐
[二分查找]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
解法一：离散化差分
分块循环处理条件二
我们可以将word拆分若干字串，相邻字符相差超过2时拆分。
变量解析
| vIndex | 记录26个字母的索引 |
| mDiff | 差分有序映射，记录那些索引是合法的完全字串的开始。合法范围必须是26个字母合法，每个字母的合法范围是：每有此字母或有k个此字母。 |
时间复杂度
O(nm1logm2),n是字符串的长度,m1是字母数，m2是mDiff的长度，不超过26*4。超时。
代码
核心代码
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.substr(pre, i - pre)); pre = i ; } } iRet += Do(word.substr(pre, word.length())); return iRet; } int Do(const string& s) { int iRet = 0; vector<vector> vIndex(26, vector(1, -1)); for (int i = 0 ; i < s.length();i++ ) { const auto& ch = s[i]; vIndex[ch - ‘a’].emplace_back(i); iRet += GetNum(vIndex,i); std::cout << “i " << i << " iRet:” << iRet << std::endl; } return iRet; } int GetNum(const vector<vector>& vIndex,int cur) { std::map<int, int> mDiff; for (int j = 0; j < 26; j++) { const auto& v = vIndex[j]; //不选择字母’a’+j mDiff[v.back()+1]++; mDiff[cur+1]–; //选择k个字母 if (v.size() > m_iK ) { //左开右闭空间 const int iMin = v[v.size() - m_iK-1]; const int iMax = v[v.size() - m_iK ]; mDiff[iMin+1]++; mDiff[iMax+1]–; } } int iCnt = 0; int iRet = 0; for ( auto it = mDiff.begin(); it != mDiff.end(); ++it ) { iCnt += it->second; if (26 == iCnt) { iRet += std::next(it)->first - it->first; } } return iRet; } 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 = “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);
}
优化
一，mDiff 不用每次都重写处理，只处理当前字母的变化。
二，vIndex 第一维用原生数组。
优化后代码
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.substr(pre, i - pre)); pre = i; } } iRet += Do(word.substr(pre, word.length())); return iRet; } int Do(const string& s) { for (int i = 0; i < 26; i++) { if( vIndex[i].empty()) { vIndex[i].emplace_back(-1); } else if(vIndex[i].size() > 1) { vIndex[i].erase(vIndex[i].begin() + 1, vIndex[i].end()); } } int iRet = 0; std::map<int, int> mDiff; mDiff[0] = 26; for (int i = 0; i < s.length(); i++) { vector<int>& v = vIndex[s[i] - 'a']; Change(v, mDiff, -1); v.emplace_back(i); Change(v, mDiff, 1); iRet += GetNum(mDiff,i); } return iRet; } void Add(std::map<int, int>& mDiff, const int index, int iChange = 1) { mDiff[index] += iChange; if (0 == mDiff[index]) { mDiff.erase(index); } } void Change(const vector<int>& v, std::map<int, int>& mDiff, int iAdd ) { Add(mDiff,v.back()+1, iAdd); if (v.size() > m_iK) { const int iMin = v[v.size() - m_iK - 1]; const int iMax = v[v.size() - m_iK]; Add(mDiff, iMin + 1, iAdd); Add(mDiff, iMax + 1, -iAdd); } } int GetNum(std::map<int, int>& mDiff,int cur) { int iCnt = 0; int iRet = 0; for (auto it = mDiff.begin(); it != mDiff.end(); ++it) { iCnt += it->second; if (26 == iCnt) { const auto itNext = std::next(it); iRet += (( mDiff.end() == itNext) ? cur+1 : std::next(it)->first) - it->first; } } return iRet; } vector<int> vIndex[26]; int m_iK; };
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
