2024-考试的最大困扰度

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

一位老师正在出一场由 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 = " _ **FFF**_ T" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "T _ **FFF**_ " 。
两种情况下，都有三个连续的 'F' 。

示例 3：

**输入：** answerKey = "TTFTTFTT", k = 1
**输出：** 5
**解释：** 我们可以将第一个 'F' 换成 'T' ，得到 answerKey = " _ **TTTTT**_ FTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTF _ **TTTTT**_ " 。
两种情况下，都有五个连续的 'T' 。

提示：

  • n == answerKey.length
  • 1 <= n <= 5 * 104
  • answerKey[i] 要么是 'T' ，要么是 'F'
  • 1 <= k <= n

方法一：滑动窗口

思路和算法

只要求最大连续指定字符的数目时，本题和「1004. 最大连续1的个数 III 」完全一致。

在指定字符的情况下，我们可以计算其最大连续数目。具体地，我们使用滑动窗口的方法，从左到右枚举右端点，维护区间中另一种字符的数量为 sum，当 sum 超过 k，我们需要让左端点右移，直到 sum} \leq k。移动过程中，我们记录滑动窗口的最大长度，即为指定字符的最大连续数目。

本题的答案为分别指定字符为 T 和 F 时的最大连续数目的较大值。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        def maxConsecutiveChar(ch: str) -> int:
            ans, left, sum = 0, 0, 0
            for right in range(len(answerKey)):
                sum += answerKey[right] != ch
                while sum > k:
                    sum -= answerKey[left] != ch
                    left += 1
                ans = max(ans, right - left + 1)
            return ans
        return max(maxConsecutiveChar('T'), maxConsecutiveChar('F'))
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxConsecutiveChar(string& answerKey, int k, char ch) {
        int n = answerKey.length();
        int ans = 0;
        for (int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += answerKey[right] != ch;
            while (sum > k) {
                sum -= answerKey[left++] != ch;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }

    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(maxConsecutiveChar(answerKey, k, 'T'),
                   maxConsecutiveChar(answerKey, k, 'F'));
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(maxConsecutiveChar(answerKey, k, 'T'), maxConsecutiveChar(answerKey, k, 'F'));
    }

    public int maxConsecutiveChar(String answerKey, int k, char ch) {
        int n = answerKey.length();
        int ans = 0;
        for (int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += answerKey.charAt(right) != ch ? 1 : 0;
            while (sum > k) {
                sum -= answerKey.charAt(left++) != ch ? 1 : 0;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int MaxConsecutiveAnswers(string answerKey, int k) {
        return Math.Max(MaxConsecutiveChar(answerKey, k, 'T'), MaxConsecutiveChar(answerKey, k, 'F'));
    }

    public int MaxConsecutiveChar(string answerKey, int k, char ch) {
        int n = answerKey.Length;
        int ans = 0;
        for (int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += answerKey[right] != ch ? 1 : 0;
            while (sum > k) {
                sum -= answerKey[left++] != ch ? 1 : 0;
            }
            ans = Math.Max(ans, right - left + 1);
        }
        return ans;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int maxConsecutiveChar(const char * answerKey, int k, char ch) {
    int n = strlen(answerKey);
    int ans = 0;
    for (int left = 0, right = 0, sum = 0; right < n; right++) {
        sum += answerKey[right] != ch;
        while (sum > k) {
            sum -= answerKey[left++] != ch;
        }
        ans = MAX(ans, right - left + 1);
    }
    return ans;
}

int maxConsecutiveAnswers(char * answerKey, int k) {
    int cnt1 = maxConsecutiveChar(answerKey, k, 'T');
    int cnt2 = maxConsecutiveChar(answerKey, k, 'F');
    return MAX(cnt1, cnt2);
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var maxConsecutiveAnswers = function(answerKey, k) {
    return Math.max(maxConsecutiveChar(answerKey, k, 'T'), maxConsecutiveChar(answerKey, k, 'F'));
}

const maxConsecutiveChar = (answerKey, k, ch) => {
    const n = answerKey.length;
    let ans = 0;
    for (let left = 0, right = 0, sum = 0; right < n; right++) {
        sum += answerKey.charAt(right) !== ch ? 1 : 0;
        while (sum > k) {
            sum -= answerKey[left++] !== ch ? 1 : 0;
        }
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func maxConsecutiveChar(answerKey string, k int, ch byte) (ans int) {
    left, sum := 0, 0
    for right := range answerKey {
        if answerKey[right] != ch {
            sum++
        }
        for sum > k {
            if answerKey[left] != ch {
                sum--
            }
            left++
        }
        ans = max(ans, right-left+1)
    }
    return
}

func maxConsecutiveAnswers(answerKey string, k int) int {
    return max(maxConsecutiveChar(answerKey, k, 'T'),
               maxConsecutiveChar(answerKey, k, 'F'))
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为字符串长度，我们只需要遍历该字符串两次。

  • 空间复杂度：O(1)，我们只需要常数的空间保存若干变量。

 Comments
On this page
2024-考试的最大困扰度