内容简介：原题地址：这道题一开始我思路错误，所以想了很久。但是其实还是标准的变宽滑动窗口题。所以，主循环类似，入窗口，出窗口思路也一样，唯一的区别就是，你不知道用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
本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
深入浅出 HTTPS：从原理到实战
虞卫东 / 电子工业出版社 / 2018-6 / 89
本书是一本专业的HTTPS书籍，全面讲解了HTTPS领域的相关知识，内容包括密码学、OpenSSL命令行、证书、TLS协议、HTTPS网站性能优化、HTTPS网站优秀实践、大型网站HTTPS架构设计等。本书有几个特点：（1）内容全面而新颖，基于RFC文档、国外书籍、社区等一手资料，总结了大部分最新的HTTPS知识；（2）由浅入深，从基础到进阶全面掌握HTTPS，读者能够轻松构建一个HTTPS网站，......一起来看看 《深入浅出 HTTPS：从原理到实战》 这本书的介绍吧!
