【leetcode详解】T3137（思路详解代码优化感悟)

本文主要是介绍【leetcode详解】T3137（思路详解代码优化感悟)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路详解

要解决这个问题，我们的大致思路是这样：找到长度为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博客