考试的最大困扰度
难度:
标签:
题目描述
代码结果
运行时间: 87 ms, 内存: 16.1 MB
/*
* 思路:
* 1. 使用Stream API并结合滑动窗口技术。
* 2. 这个版本利用Stream的特性,虽然不像传统代码那样直观,但能体现函数式编程的风格。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxConsecutiveAnswers(String answerKey, int k) {
return Math.max(maxConsecutiveChar(answerKey, k, 'T'), maxConsecutiveChar(answerKey, k, 'F'));
}
private int maxConsecutiveChar(String answerKey, int k, char ch) {
int[] maxLen = {0};
IntStream.range(0, answerKey.length()).forEach(left -> {
int[] count = {0};
IntStream.range(left, answerKey.length()).forEach(right -> {
if (answerKey.charAt(right) != ch) count[0]++;
if (count[0] > k) return;
maxLen[0] = Math.max(maxLen[0], right - left + 1);
});
});
return maxLen[0];
}
}
解释
方法:
此题解采用的是滑动窗口技术来求解问题。主要目标是找到最长的可以通过至多k次变换得到全T或全F的子串。在滑动窗口中,通过两个计数器cntB和cntA分别统计窗口内T和F的数量。窗口从左向右扩展,每次循环读入一个新的字符,并相应地更新计数器。如果窗口内T的数量超过k且F的数量也超过k,则说明当前窗口内无法通过k次变换变为全T或全F。此时需要移动窗口的左边界left,即缩小窗口,直到窗口内的T或F的数量能够被k次操作覆盖。最终,最大的滑动窗口长度即为所求的最大连续字符数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法中,为什么选择滑动窗口技术来解决这个问题,而不是其他可能的方法比如动态规划?
▷🦆
该题解中窗口的大小是如何决定的?是否有可能窗口大小固定导致无法找到最大解?
▷🦆
请问为什么当`cntB > k` 和 `cntA > k` 时,我们需要缩小窗口?这里的逻辑是基于什么原理?
▷🦆
在缩小窗口的操作中,为什么只是简单地移动左边界而不考虑右边界的移动?
▷