思路详解
要解决这个问题,我们的大致思路是这样:找到长度为k的字符串 (记为stringA) ,统计重复次数最多的那一个,则最终对应的k周期字符串就是 [stringA * n] 的形式( n = word.length() / k)
要实现多对象的计数,map是一个很好的选择
unordered_map<string, int>mp;//字符串, 出现次数
根据上面的调整后的最终形式不难发现,stringA 还应满足位置条件,即起始位置必须在k的整数倍上。
于是咱们的for循环就以k为递增周期
for(int i=0; i<word.length(); i+=k)
初步的代码实现如下:
class Solution {
public:int minimumOperationsToMakeKPeriodic(string word, int k) {if(word.length() == k) return 0;unordered_map<string, int>mp;int re = 0, mx = 1;string cur;for(int i=0; i<=word.length()-k; i+=k){cur = word.substr(i, k);if(mp.find(cur) != mp.end()){mp[cur]++;mx = max(mx, mp[cur]); }else{mp[cur] = 1;}}return word.length()/k - mx; }
};
代码优化
由于笔者见识太有限了,上面的代码虽AC,但双复杂度双高
观摩了其他大佬的写法,同样的思路,不同的语法实现,提交后直接逼近双百了!
下面分享下笔者的感悟:
笔者自己感觉,自己最开始的代码时间上吃亏在了 cur = word.substr(i, k); 这一调用.substr()函数截取长度为k字符串的操作上。同时,也增加了一个cur的存储空间,加重了空间复杂度的负担。
更好的程序是运用了string_view类型来构建map,可以在大大减少存储空间的情况下便利某段字符串的访问
//更多关于string 和 string_view的区别的讨论,推荐参考文章:
【C++干货】高效能的 string_view 和扎实稳定的 string-CSDN博客
出色的代码见下,真是简明干练,佩服!
class Solution {
public:int minimumOperationsToMakeKPeriodic(string word, int k) {unordered_map<string_view, int>mp;for(int i=0; i<=word.length()-k; i+=k)mp[{word.c_str()+i, word.c_str()+i+k}]++;//不存在的键对应的值默认是0return word.length()/k - max_element(mp.begin(), mp.end(), [](auto& a, auto& b){return a.second < b.second;})->second; //lambda表达式,相当于构建了一个cmp函数}
};
//关于lambda表达式的基本用法,推荐参考文章:
【C++浅析】lambda表达式:基本结构 & 使用示例-CSDN博客