赞
踩
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
注意:
字符串长度 和 k 不会超过
示例 1:
- 输入:
- s = "ABAB", k = 2
-
- 输出:
- 4
-
- 解释:
- 用两个'A'替换为两个'B',反之亦然。
示例 2:
- 输入:
- s = "AABABBA", k = 1
-
- 输出:
- 4
-
- 解释:
- 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
- 子串 "BBBB" 有最长重复字母, 答案为 4。
题目来源:LeetCode 链接:https://leetcode-cn.com/problems/longest-repeating-character-replacement
1.暴力法,一般时间都会超限
- class Solution {
- public:
- int characterReplacement(string s, int k) {
- int k2=k, maxlen=0, first=s.length();
- int i=0, j=0; //一个左边界i,一个右边界j
- while(i<s.length()&&j<s.length())
- {
- if(s[j]!=s[i])
- {
- if(k2>0)
- {
- k2--;
- first = first< j ? first: j; //first记录第一个跟s[i]不相同的元素下标
- //后面可以直接把i重新赋值为first,而不是i+1
- j++;
- }
- else //如果k次修改机会用完
- {
- int temp = j-i;
- maxlen = maxlen<temp?temp:maxlen; //记录最长字符串长度
- if((s.length()-first)>maxlen) //只有first后面的字符串大于目前的maxlen
- { //继续执行才有意义,否则直接break
- i = first; //把i赋值为first
- j = i+1; //j为i+1
- k2 = k; //k2复原为原值
- }
- else
- break;
- }
- }
- else
- {
- j++;
- }
- int temp = j-i;
- maxlen = maxlen<temp?temp:maxlen;
- }
- return maxlen;
- }
- };
2.滑动窗口法
上面的暴力法最坏情况了的时间复杂度其实可以达到
该方法时记录滑动窗口内的最多个数的字符即charMax,只要满足right - left + 1 > charMax + k即可继续向右扩张,即right++,不满足的时候就窗口整体向右移动,即同时right++,left++。这时候,假设后面都没有更长的替换后连续字符串的话,那么这个窗口长度会一直不变,知道循环结束(right走到终点),而如果后面还有更长的替换后连续字符串的话,这个窗口就会再次扩张。最后返回窗口大小,就是所求的替换后最长连续字符串的长度。
- class Solution {
- public:
- int characterReplacement(string s, int k) {
- if(s.length()==0)
- return 0;
- int map[26]={0}; //map用来记录字符数
- int i=0, charmax=0; //map数组下标为键,内容为值
- for(int j=0;j<s.length();j++)
- {
- int index = s[j]-'A';
- map[index]++; //向右扩张一步
- charmax=charmax>map[index]?charmax:map[index]; //更新charmax
- if((j-i+1)>charmax+k)
- {
- map[s[i]-'A']--; //如果不符合条件,左边收缩
- //保持窗口长度不变
- i++;
- }
- }
- return s.length()-i;
- }
- };
三、总结
1.滑动窗口通常由扩张、收缩、移动三种行为,根据解题过程的不同阶段采取不同的行为
2.滑动窗口经常搭配map使用 ,意在记录滑动窗口中的信息
3.滑动窗口很适合解决字符串类的题目
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。