LeetCode 第424题 Longest Repeating Character Replacement【滑动窗口】(Java)

原题地址: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

本文假设你对滑动窗口概念有所了解,如果你对滑动窗口的概念不够了解,请参看我介绍滑动窗口的文章,里面有详细的解释

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据