内容简介：原题地址：这道题一开始我思路错误，所以想了很久。但是其实还是标准的变宽滑动窗口题。所以，主循环类似，入窗口，出窗口思路也一样，唯一的区别就是，你不知道用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
本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
图论算法理论、实现及应用
王桂平//王衍//任嘉辰 / 北京大学 / 2011-1 / 54.00元
《图论算法理论、实现及应用》系统地介绍了图论算法理论，并选取经典的ACM／ICPC竞赛题目为例题阐述图论算法思想，侧重于图论算法的程序实现及应用。《图论算法理论、实现及应用》第1章介绍图的基本概念和图的两种存储表示方法：邻接矩阵和邻接表，第2～9章分别讨论图的遍历与活动网络问题，树与图的生成树，最短路径问题，可行遍性问题，网络流问题，支配集、覆盖集、独立集与匹配，图的连通性问题，平面图及图的着色问......一起来看看 《图论算法理论、实现及应用》 这本书的介绍吧!
