526互联

[LeetCode] 2024. Maximize the Confusion of an Exam

发布时间 2023-07-07 09:16:38作者: CNoodle

A teacher is writing a test with n true/false questions, with 'T' denoting true and 'F' denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).

You are given a string answerKey, where answerKey[i] is the original answer to the ith question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:

  • Change the answer key for any question to 'T' or 'F' (i.e., set answerKey[i] to 'T' or 'F').

Return the maximum number of consecutive 'T's or 'F's in the answer key after performing the operation at most k times.

Example 1:

Input: answerKey = "TTFF", k = 2
Output: 4
Explanation: We can replace both the 'F's with 'T's to make answerKey = "TTTT".
There are four consecutive 'T's.

Example 2:

Input: answerKey = "TFFT", k = 1
Output: 3
Explanation: We can replace the first 'T' with an 'F' to make answerKey = "FFFT".
Alternatively, we can replace the second 'T' with an 'F' to make answerKey = "TFFF".
In both cases, there are three consecutive 'F's.

Example 3:

Input: answerKey = "TTFTTFTT", k = 1
Output: 5
Explanation: We can replace the first 'F' to make answerKey = "TTTTTFTT"
Alternatively, we can replace the second 'F' to make answerKey = "TTFTTTTT". 
In both cases, there are five consecutive 'T's. 

Constraints:

  • n == answerKey.length
  • 1 <= n <= 5 * 104
  • answerKey[i] is either 'T' or 'F'
  • 1 <= k <= n

考试的最大困扰度。

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。
请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximize-the-confusion-of-an-exam
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是滑动窗口。题意是老师想把题目的答案出成一串 TRUE 或者一串 FALSE 让学生增加对自己的答案的不确定性，同时给了一个变量 K，允许你修改原答案里的 K 个答案以得到一串全局最长的 T或者 F。这道题转译一下就是在 input 字符串里面找一段最长的 T 或者最长的 F，其中允许你修改其中的 K 处字母，请你求全局最长的连续子串的长度。这道题我们需要用两次滑动窗口，一次看最长的由 T 组成的子串的长度，一次看最长的由 F 组成的子串的长度。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int maxConsecutiveAnswers(String answerKey, int k) {
 3         int numOfTrue = helper(answerKey, k, 'T');
 4         int numOfFalse = helper(answerKey, k, 'F');
 5         return Math.max(numOfTrue, numOfFalse);
 6     }
 7     
 8     private int helper(String s, int k, char target) {
 9         int start = 0;
10         int end = 0;
11         int count = 0;
12         int res = 0;
13         while (end < s.length()) {
14             if (s.charAt(end) != target) {
15                 k--;
16             }
17             end++;
18             while (k < 0) {
19                 if (s.charAt(start) != target) {
20                     k++;
21                 }
22                 start++;
23             }
24             res = Math.max(res, end - start);
25         }
26         return res;
27     }
28 }

 

LeetCode 题目总结