悲伤，一开始一点想法都没有，纠结于具体的更改方式，比如，给出[aba]，k=1，如何成功找到b，让它变成a，然后可以得到最长重复为3。但是一直困扰于其算法实现的复杂度。看了看discuss，发现它是用滑窗的方式来计算的，返回最大窗长。具体思路为： 给出一个窗口，计算窗口中所有字符的个数n，并且统计窗口中出现次数最多的字符个数maxFre。如果n-maxFre大于等于可以更改的字符数k，那么这个窗就是个好窗。否则对窗户进行缩小，找到合适的窗口大小。
但是实际写代码的过程中，依旧有地方困扰着我。例如maxFre并不是[start,end]区间上出现重复次数最多的个数。而是存储历史最大maxFre。也就是说，窗长一直会在增长。只有所在区间的重复频率大于maxFre时，窗长才会增长。、 amazing。。。感觉很巧妙啊，非常规题目。
class Solution {public: int characterReplacement(string s, int k) { int begin=0; int end=-1; int maxFre=0; int maxLength=0; map<char,int> count; while(1) { end++;//[start,end] if(end>=s.length()) break; //maxFre=findMaxFre(s,begin,end); count[s[end]]++; if(maxFre<count[s[end]]) maxFre=count[s[end]]; //cout<<begin<<" "<<end<<endl; while(end-begin+1-maxFre>k) { count[s[begin]]--; begin++; } if(maxLength<end-begin+1) maxLength=end-begin+1; } return maxLength; }};新闻热点
疑难解答
