以最左边为开始,往右遍历,不一样的个数大于K的时候停止,回到第一个不一样的地方,以它为开始,继续。。
用QUEUE记录每次不一样的INDEX,以便下一个遍历开始,
从左往右,从右往左各来一次。。加上各种剪枝情况,比如未遍历的数量<剩余K的数量,比如已经记录过某个INDEX了。。
然后TLE了。。。最后放TLE的方法。。不知道有什么意义。。
上面的做法是左右各来一次,那是否可以使用滑窗呢。。
然后没做出来。。看了讨论区。。果然是滑窗。。
思路:
统计当前滑窗内最多的字母,窗口宽度 - 最多字母数量 <= K,就可以继续尝试扩大窗口,R++。 否则缩小,L++。
比我一开始的那个傻逼办法的改进在于,自动转换字母,我那个必须记录不同字母,比如AAABBBBB当B多的时候,必须退回到第一个B,重新遍历。。而且不用反向再来一次。
至少。。我。。猜对。。滑。。滑窗。。了。。
public class Solution
{
public int characterReplacement(String s, int k)
{
int[] letter = new int[26];
int l = 0;
int most = ++letter[s.charAt(0) - 'A'];
int res = 1;
for(int r = 1; r < s.length();r++)
{
most = Math.max(most,++letter[s.charAt(r) - 'A']);
if(most + k < r - l + 1) // can't maintain this size of window
{
letter[s.charAt(l++)-'A']--;
}
res = Math.max(res,r-l+1);
}
return res;
}
}
二刷。
这个题刚做的,还有印象,滑窗。
但是凭印象做完,回头看这个做法非常巧妙。
我还记得一开始的思路是滑窗,但是做不出来,当时的想法是:
最多的字母 + Others(k) = Length
每次滑窗扩大都需要统计最多的字母,然后相应地要改变Others(或者不改变),再和K比较,决定窗口的左端是否缩进,然后缩进又会减少相应的字母,又要重新判断最多的字母。。。此时右端保持不动。。。
这里忽略了一个问题就是,缩进的目的有2个,一个是通过减少不一样的字母(others)来满足others <= k;或者通过改变最多的字母(most)来满足others <= k,因为只有在满足的情况下我们才会更新res的最大值。 简而言之,通过不停地让窗口左端缩进,目的只有一个others <= k,一旦这个满足我们就可以update res,但是,既然我们都他妈缩进了,肯定比前面的结果小,还更新个鸡巴。。
这里巧妙就巧妙在,左边缩进的同时右边扩大,因为窗口再变小即使满足others <= k,窗口大小也是小于res的,so why bother...and who gives a shit..所以直接右边扩大就行了。。
一开始的想法是尽量满足others <= k的时候判断窗口大小;
后来的做法是保持窗口>当前最大值res的情况下,我们才看是否满足others <= k,满足才更新。。
这些问题一刷都没想,光觉得卧槽这个做法牛逼啊。
其实二刷仔细想想,才发现,确实牛逼啊
public class Solution {
public int characterReplacement(String s, int k) {
if (s.length() == 0) return 0;
int[] map = new int[26];
int most = ++map[s.charAt(0) - 'A'];
int res = 1;
int left = 0;
for (int right = 1; right < s.length(); right++) {
most = Math.max(most,++map[s.charAt(right) - 'A']);
if (right - left + 1 > most + k) {
map[s.charAt(left++) - 'A']--;
} else {
res = Math.max(res,right - left + 1);
}
}
return res;
}
}
三刷。
脑残啊卧槽,又忘了怎么做了。
windowSize - numOfMajorityElement <= K
主要就是这行,满足的时候更新windowSize,
不满足的时候减少windowSize,减少之后numOfMajorityElement也会变,但是不会变大。
public class Solution {
public int characterReplacement(String s, int k) {
if (s.length() == 0) return 0;
int res = 0;
int l = 0;
int[] letters = new int[26];
int maj = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
maj = Math.max(maj, ++ letters[c -'A']);
int winSize = r - l + 1;
if (winSize - maj <= k) {
res = Math.max(winSize, res);
} else {
letters[s.charAt(l++) - 'A'] --;
}
}
return res;
}
}