内容简介：原题地址：这道题一开始我思路错误，所以想了很久。但是其实还是标准的变宽滑动窗口题。所以，主循环类似，入窗口，出窗口思路也一样，唯一的区别就是，你不知道用A替换B好，还是用B替换A好。所以，每次字符入窗口，我们需要统计，替换字数是多少。而替换字数一定是，出现频率高的字符不替换，只替换出现频率低的字符。比如，ABCCD，可以替换三个字符的话，我们一定是CC不变，替换ABD为C。当替换字数大于k的时候，我们就要移动left，让一个字符出窗口。
原题地址： https://leetcode.com/problems/longest-repeating-character-replacement/
要求：
给定字符串只包含大写英文字母，你可以替换任意一个字母，替换最多k次。找到这样操作后，最长的全部都是重复字符的子串长度来。
注意: 字符和k的长度都不到104。
例 1:
输入:
s = “ABAB”, k = 2
输出:
4
把两个A换成B，或者反之
例 2:
输入:
s = “AABABBA”, k = 1
输出:
4
把中间的A换成B，那么字符串变成”AABBBBA”，其中”BBBB”长度为4。
这道题一开始我思路错误，所以想了很久。但是其实还是标准的变宽滑动窗口题。所以，主循环类似，入窗口，出窗口思路也一样，唯一的区别就是，你不知道用A替换B好，还是用B替换A好。
所以，每次字符入窗口，我们需要统计，替换字数是多少。而替换字数一定是，出现频率高的字符不替换，只替换出现频率低的字符。比如，ABCCD，可以替换三个字符的话，我们一定是CC不变，替换ABD为C。当替换字数大于k的时候，我们就要移动left，让一个字符出窗口。
所以，主函数characterReplacement的结构很眼熟。
然后是replaceCount，计算当前的窗口需要替换几个字符，才能变成全都一样的字符：
这道题的速度也一般，30ms，应该是replaceCount函数有很大优化的余地吧。
本题代码地址为： https://github.com/tinyfool/leetcode/tree/master/src/p0424
本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Pattern Recognition and Machine Learning
Christopher Bishop / Springer / 2007-10-1 / USD 94.95
The dramatic growth in practical applications for machine learning over the last ten years has been accompanied by many important developments in the underlying algorithms and techniques. For example,......一起来看看 《Pattern Recognition and Machine Learning》 这本书的介绍吧!
