2024. 考试的最大困扰度
2024-09-01 本文已影响0人
红树_
晚上不睡，白天崩溃。昨天周末去大学看发现9.1号刚好碰上新生入学了！
题目
LC每日一题，参考2024. 考试的最大困扰度 - 力扣（LeetCode）
，难度分1643 中等。
解题思路
-
滑动窗口：考虑过动态规划发现无法关联连续相同字符，想到贪心发现替换肯定是连续的不会分隔的肯定需要使用滑动窗口，关键点是怎么定义窗口范围，找规律可以发现如果窗口包含的两种字符数量有一种小于等于
k则可把其全部替换为该字符满足题目条件可以计算为一个临时答案。
滑动窗口 9ms 94.38%
class Solution {
public int maxConsecutiveAnswers(String answerKey, int k) {
char[] cs = answerKey.toCharArray();
int n = cs.length, res = 0;
// 参考滑动窗口解法
int l = 0, r = 0;// 窗口先增加r右指针，如果不满足min(tN,fN)<=k则l增加左指针开始右移
int tN = 0, fN = 0; // 窗口当前F、N的数量
while (r < n) { // 右指针遍历
if(cs[r] == 'T') {
tN++;
} else {
fN++;
}
while (l < r && tN > k && fN > k) { // 开始减小窗口 左指针右移动
if (cs[l] == 'T') {
tN--;
} else {
fN--;
}
l++;
}
res = Math.max(res, r - l + 1);// 当前窗口满足条件 计算一个备选结果
r++;
}
return res;
}
}
复杂度分析
- 时间复杂度：
O(n)，左右指针都最多遍历字符串一次，n为字符串长度。 - 空间复杂度：
O(1)，只使用了常量个变量空间。
2024-9-2
