Code & Fun

第6天, 下雨了。。。。

今天的题目是Longest Repeating Character Replacement

emmmm,这道题一开始的解法虽然AC了,但是时间复杂度是O(n^2),但是最佳解法却是O(n),先看下我的解法:

思路比较简单,就是不断以某个字符为起始,以这个字符为目标,计算修改k次后能达到的长度,然而这样会有个问题,例如ABBB,如果k为1的话,我计算出来是3,但真实结果是4

为了解决这个问题,我增加了一次判断,对前k个字符进行替换,替换成下一个字符,即以下一个字符为目标,计算修改k次后能达到的长度。

具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int characterReplacement(string s, int k) {
int len = s.size();
int res = 0;
int j, a;
for(int i = 0; i < len; i++) {
char c = s[i];
a = k;
for(j = i+1;j < len; j++) {
if (c != s[j]) {
if (a == 0) break;
else a--;
}
}
res = max(j-i, res);
}

for(int i = 0;i < k && i+1 < len; i++) {
char c = s[i+1];
a = k-i-1;
for(j = i + 2;j < len; j++) {
if (c != s[j]) {
if (a == 0) break;
else a--;
}
}
res = max(j-i, res);
}

return res;
}
};

OK,现在可以忽略掉上面的解法了,看看O(n)的解法是怎样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int characterReplacement(string s, int k) {
vector<int> ch(26);
int start = 0, end = 0, max_count = 0;
int len = s.size();
while(end < len) {
ch[s[end] - 'A']++;
// update max_count
max_count = max(max_count, ch[s[end]-'A']);
end++;
if ( end - start > max_count + k) {
ch[s[start] - 'A']--;
start++;
}
}
return end - start;
}
};

很精妙的用滑窗解决了这个问题:

首先,它用一个数组记录滑窗内的出现字符的个数,因此每次迭代或操作都向前移动一个字符而已,所以我们可以很容易维护出一个max_count,即所有字符出现次数最大的那一个。

然后如果是一个正确的解的话,要满足一个约束end - start - k > max_count,如果满足的话,可以增大滑窗去寻找更大的窗口,如果不行,那么我们就向前移动滑窗。

虽然在迭代结束后,我们不能保证当前滑窗就是满足约束的解,但是我们可以保证,最大的窗口大小一定和我们现在的滑窗大小是一样的,故可以得到解。


本文首发于Code & Fun