内容简介：原题地址：这道题一开始我思路错误，所以想了很久。但是其实还是标准的变宽滑动窗口题。所以，主循环类似，入窗口，出窗口思路也一样，唯一的区别就是，你不知道用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
本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Perl入门经典
[美]Curtis "Ovid" Poe / 朱允刚、韩雷、叶斌 / 清华大学出版社 / 2013-9-20 / 78.00
作为最有影响力的编程语言之一，Perl被广泛用在Web开发、数据处理和系统管理中。无论是Perl新手，还是想要加强自己实战技能的Perl程序员，《Perl入门经典》都提供了处理日常情况所需的各种技术。凭借十多年的Perl经验，作者Curtis“Ovid”Poe一开始先简单回顾了Perl的基础知识，然后以此为出发点，举例说明了Perl在工作场所中的各种真实用法。此外，书中还包含了一些动手练习、宝贵建......一起来看看 《Perl入门经典》 这本书的介绍吧!
