题意:
给出只含有两种字符的 字符串 以及一个次数限制k,问最多修改k个位置(T->F/F->T),最大的连续的字符串的长度是多少
思路:
双指针/ 滑动窗口
假如说我们要找修改后连续的T最长的长度,我们可以{
- 枚举右端点,并统计当前不等于’T’的字符串的个数,并且统计数量,记为c n t cntcnt
- 如果说左区间到右区间的c n t cntcnt 是否 小于等于 k{
(1)如果说数量上大于k了,就只能让左端点向右,并记录cnt的减小情况,直到cnt <= k
}
过程中统计区间长度并记录最大值
}
Code:
class Solution { public: int maxConsecutiveAnswers(string answerKey, int k) { int ans = 0; int l = 0,r = 0,cnt = 0; int len = answerKey.size(); for(r = 0;r < len;r ++) { cnt += (answerKey[r] != 'T' ? 1:0); while(cnt > k) { if(answerKey[l] != 'T') cnt --; ++ l; } ans = max(ans, r - l + 1); } l = 0,r = 0,cnt = 0; for(r = 0;r < len;r ++) { cnt += (answerKey[r] != 'F' ? 1:0); while(cnt > k) { if(answerKey[l] != 'F') cnt --; ++ l; } ans = max(ans, r - l + 1); } return ans; } };
文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树leetcode-双指针75-颜色分类8282 人正在系统学习中