推 a1234555: 大師 07/08 01:57
推 Che31128: 大師 07/08 01:57
※ 編輯: Rushia (122.100.75.86 臺灣), 07/08/2023 02:06:37
https://leetcode.com/problems/maximize-the-confusion-of-an-exam/description/
2024. Maximize the Confusion of an Exam
一個教師正在編寫包含 n 個是非題的試卷，T 表示真 F 表示假。
他想透過最大化具有相同答案的連續問題數量（多個連續T或F）來迷惑學生。給你一
個字串 answerKey 表示第 i 個問題的原始答案，此外再給你一個整數 k 表示可以執行
以下操作的次數：
* 將任何問題的答案更改為 T 或 F
執行最多 k 次操作後，返回答案中連續 T 或 F 的最大數量。
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.
思路：
1.找最長連續子序列我先想到滑動窗口，先找全為T最長可以多長， 再來找全為F的，簡
單暴力。
2.過程就是還有 k 可以用或是下一個字元是目標字元的時候就一直把字元 push 進窗口
，否則一直 pop 最左元素直到窗口內元素合法。
Java Code：
--------------------------------------
class Solution {
public int maxConsecutiveAnswers(String answerKey, int k) {
int res = 0;
res = Math.max(res, helper(answerKey, 'T', k));
res = Math.max(res, helper(answerKey, 'F', k));
return res;
}
private int helper(String answerKey, char c, int k) {
int res = 0;
int n = answerKey.length();
int l = 0, r = 0;
while (r < n) {
if (answerKey.charAt(r) == c) {
if (k > 0) k--;
else {
while (answerKey.charAt(l) != c) {
l++;
}
l++;
}
}
res = Math.max(res, r - l + 1);
r++;
}
return res;
}
}
--------------------------------------
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1688752550.A.648.html