内容简介：原题地址：这道题一开始我思路错误，所以想了很久。但是其实还是标准的变宽滑动窗口题。所以，主循环类似，入窗口，出窗口思路也一样，唯一的区别就是，你不知道用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
本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
视觉SLAM十四讲
高翔、张涛、等 / 电子工业出版社 / 2017-3 / 75
《视觉SLAM十四讲：从理论到实践》系统介绍了视觉SLAM（同时定位与地图构建）所需的基本知识与核心算法，既包括数学理论基础，如三维空间的刚体运动、非线性优化，又包括计算机视觉的算法实现，例如多视图几何、回环检测等。此外，还提供了大量的实例代码供读者学习研究，从而更深入地掌握这些内容。 《视觉SLAM十四讲：从理论到实践》可以作为对SLAM 感兴趣的研究人员的入门自学材料，也可以作为SLAM......一起来看看 《视觉SLAM十四讲》 这本书的介绍吧!
