【面试高频题】难度 1.5/5,常规滑动窗口运用题
2023-02-19 12:17:50 时间
题目描述
这是 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 原题链接和其他优选题解。
相关文章
- 一文教会你mock(Mockito和PowerMock双剑合璧)
- Go语言性能剖析利器--pprof实战
- Linux内存泄露案例分析和内存管理分享
- 通过linux-PAM实现禁止root用户登陆的方法
- Linux策略路由详解
- 理解virt、res、shr之间的关系(linux系统篇)
- oracle学习笔记(十六) PL/SQL 异常和goto语句
- Linux云主机安全入侵排查步骤
- PHP官方框架 Zend Framework 2.1 发布
- PHP 5.4 内置Web服务器使用说明
- 一个小巧的PHP防注入类
- PHPCMS后台入口地址隐藏方法
- 在Linux中将目录压缩打包为zip文件 并通过ftp上传的Shell脚本
- 用PHP解析XML为数组的方法
- 一段经典的抽奖算法 for PHP版
- 在Linux中用Shell脚本完成SVN版本库的建立
- PHPCMS V9无法正常通过QQ登录的解决方案
- 解决Nginx环境下PHP的flush失效问题
- 用SS5在Linux上搭建Socks5 Proxy代理服务器
- Linux中编译安装Redis和PHP扩展