leetcode
leetcode 1751 ~ 1800
考试的最大困扰度

考试的最大困扰度

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在算法中,为什么选择滑动窗口技术来解决这个问题,而不是其他可能的方法比如动态规划?
滑动窗口技术适用于处理数组或字符串中的连续子区间的问题,特别是当需要优化时间复杂度以达到线性时间处理时。对于本题,目标是找到最长的子串,使得该子串通过至多k次变换可以全部变为'T'或全部变为'F'。使用滑动窗口,我们可以有效地在一次遍历中动态调整窗口大小,以找到满足条件的最长子串。相比之下,动态规划可能需要更复杂的状态表示和转移,而且时间和空间复杂度通常会更高,不如滑动窗口方法直观和高效。
🦆
该题解中窗口的大小是如何决定的?是否有可能窗口大小固定导致无法找到最大解?
在这个题解中,窗口的大小是动态调整的,而不是固定的。窗口从左向右滑动,每次读入一个新的字符扩展窗口的右边界,同时根据条件调整左边界以保证窗口内最多只需要k次变换即可全部变为'T'或'F'。这种动态调整策略确保能覆盖所有可能的最大窗口,因此不存在因窗口大小固定而无法找到最大解的问题。
🦆
请问为什么当`cntB > k` 和 `cntA > k` 时,我们需要缩小窗口?这里的逻辑是基于什么原理?
当`cntB > k`和`cntA > k`时,意味着窗口内的'T'数量和'F'数量都超过了可以通过k次变换来统一的限制。这说明当前窗口无法通过至多k次变换成为全部'T'或全部'F'。因此,需要缩小窗口以尝试减少一个字符类型的数量,使得剩余的字符数量可以被k次变换覆盖。这是为了找到一个合法的子串,即窗口内的字符可以通过至多k次变换全部统一。
🦆
在缩小窗口的操作中,为什么只是简单地移动左边界而不考虑右边界的移动?
在这种滑动窗口策略中,右边界总是在每次迭代中向右移动,以尝试包含更多的字符来找到可能的最长有效子串。当发现当前窗口不再符合条件时(即`cntB > k`和`cntA > k`),移动左边界是为了尝试减小窗口内部的字符计数,使窗口再次符合条件。右边界已经尽可能地扩展了,再移动右边界只会减少窗口大小,无助于寻找更长的有效子串。因此,调整左边界是缩小窗口的合理选择。

相关问题