题目描述
这是 LeetCode 上的 2024. 考试的最大困扰度 ,难度为 中等。
Tag : 「滑动窗口」、「双指针」
一位老师正在出一场由 道判断题构成的考试,每道题的答案为
true
(用 'T'
表示)或者 false
(用 'F'
表示)。老师想增加学生对自己做出答案的不确定性,方法是最大化有连续相同结果的题数。(也就是连续出现 true
或者连续出现 false
)。
给你一个字符串 ,其中
是第
个问题的正确结果。除此以外,还给你一个整数
,表示你能进行以下操作的最多次数:
每次操作中,将问题的正确答案改为 'T'
或者 'F'
(也就是将 改为
'T'
或者 'F'
)。
请你返回在不超过 次操作的情况下,最大 连续
'T'
或者 'F'
的数目。
示例 1:
输入:answerKey = "TTFF", k = 2
输出:4
解释:我们可以将两个 'F' 都变为 'T' ,得到 answerKey = "TTTT"
示例 2:
输入:answerKey = "TFFT", k = 1
输出:3
解释:我们可以将最前面的 'T' 换成 'F' ,得到 answerKey = "FFFT" 。
或者,我们可以将第二个 'T' 换成 'F' ,得到 answerKey = "TFFF"
示例 3:
输入:answerKey = "TTFTTFTT", k = 1
输出:5
解释:我们可以将第一个 'F' 换成 'T' ,得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ,得到 answerKey = "TTFTTTTT"
提示:
要么是
'T'
,要么是'F'
滑动窗口
题目求修改次数不超过 的前提下,连续段
'T'
或 'F'
的最大长度。
等价于求一个包含 'F'
或者 'T'
的个数不超过
假定存在一个 int getCnt(char c)
函数,返回包含字符 c
数量不超过 的最大窗口长度,那么最终
max(getCnt('T'), getCnt('F'))
即是答案。
其中 getCnt
函数的实现可以使用「滑动窗口」:使用 和
分别代表窗口的左右端点,
为区间
中的字符
c
的数量,每次右端点 移动时,若满足
,让
自增,当
时,使左端点
往右移动,同时更新
,直到
区间恢复合法性(包含字符
c
的数量 不超过
代码:
class Solution {
String s;
int n, k;
public int maxConsecutiveAnswers(String answerKey, int {
s = answerKey;
n = s.length(); k = _k;
return Math.max(getCnt('T'), getCnt('F'));
}
int getCnt(char {
int ans = 0;
for (int i = 0, j = 0, cnt = 0; i < n; i++) {
if (s.charAt(i) == c) cnt++;
while (cnt > k) {
if (s.charAt(j) == c) cnt--;
j++;
}
ans = Math.max(ans, i - j + 1);
}
return
- 时间复杂度:
- 空间复杂度:
最后
这是我们「刷穿 LeetCode」系列文章的第 No.2024
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。