【面试高频题】难度 1.5/5,常规滑动窗口运用题
面试 窗口 运用 高频 滑动 1.5 难度 常规
2023-06-13 09:16:25 时间
题目描述
这是 LeetCode 上的「2024. 考试的最大困扰度」,难度为「中等」。
Tag : 「滑动窗口」、「双指针」
一位老师正在出一场由 n道判断题构成的考试,每道题的答案为 true
(用 'T'
表示)或者 false
(用 'F'
表示)。老师想增加学生对自己做出答案的不确定性,方法是最大化有连续相同结果的题数。(也就是连续出现 true
或者连续出现 false
)。
给你一个字符串 answerKey,其中 answerKey[i]是第 i个问题的正确结果。除此以外,还给你一个整数 k,表示你能进行以下操作的最多次数:
每次操作中,将问题的正确答案改为 'T'
或者 'F'
(也就是将 answerKey[i] 改为 'T'
或者 'F'
)。请你返回在不超过 k 次操作的情况下,最大 连续 'T'
或者 'F'
的数目。
示例 1:
输入:answerKey = "TTFF", k = 2
输出:4
解释:我们可以将两个 'F' 都变为 'T' ,得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。
示例 2:
输入:answerKey = "TFFT", k = 1
输出:3
解释:我们可以将最前面的 'T' 换成 'F' ,得到 answerKey = "FFFT" 。
或者,我们可以将第二个 'T' 换成 'F' ,得到 answerKey = "TFFF" 。
两种情况下,都有三个连续的 'F' 。
示例 3:
输入:answerKey = "TTFTTFTT", k = 1
输出:5
解释:我们可以将第一个 'F' 换成 'T' ,得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ,得到 answerKey = "TTFTTTTT" 。
两种情况下,都有五个连续的 'T' 。
提示:
代码:
class Solution {
String s;
int n, k;
public int maxConsecutiveAnswers(String answerKey, int _k) {
s = answerKey;
n = s.length(); k = _k;
return Math.max(getCnt('T'), getCnt('F'));
}
int getCnt(char c) {
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 ans;
}
}
- 时间复杂度:
- 空间复杂度:
最后
这是我们「刷穿 LeetCode」系列文章的第 No.2024
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
相关文章
- 软件测试面试题及答案2020_软件测试面试题目100及最佳答案
- 校招生如何准备面试?
- vue面试考察知识点全梳理
- 面试系列-spring-ioc原理
- 前端刷完这12道滑动窗口,是不是就可以出山面试了
- 2022最新Spring面试必问填空题 看看你都会几个
- BAT面试算法进阶(3)- 无重复字符的最长子串(滑动窗口法)
- BAT面试算法进阶(6)- 最长回文子串(方法二)
- 题突破Oracle六大面试题,轻松跨入IT行业(oracle六大面试)
- MySQL面试100道超强挑战题(100道mysql面试题)
- 分布式Redis面试挑战提升你的职业技能(分布式redis面试题)
- 如何突出你的Redis面试(redis面试怎么样)
- 红色体验面试Redis知识答题卡(redis 面试卡)