文章目录
- 题目描述
- 简化题目
- 思路分析
- 完整代码
题目描述
一位老师正在出一场由 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 = “FFFT” 。
或者，我们可以将第二个 ‘T’ 换成 ‘F’ ，得到 answerKey = “TFFF” 。
两种情况下，都有三个连续的 ‘F’ 。
示例 3：
输入：answerKey = “TTFTTFTT”, k = 1
输出：5
解释：我们可以将第一个 ‘F’ 换成 ‘T’ ，得到 answerKey = “TTTTTFTT” 。
或者我们可以将第二个 ‘F’ 换成 ‘T’ ，得到 answerKey = “TTFTTTTT” 。
两种情况下，都有五个连续的 ‘T’ 。
简化题目
给你一个字符串 里面都是‘T’或者‘F’，你可以将其中k个字符由T变成F 或者 由F变成T，使得F或T的连续个数最多。
思路分析
这题直接滑动窗口可以做，俩指针维护一个窗口，假设现在将F变成T，统计窗口中F的个数，只要不大于k个，就一直挪动右指针，否则挪动左指针直到窗口中的F的个数等于k，期间记录窗口长度最大值即可。
我们需要检测 T变成F的情况和F变成T的情况，取他俩的最大长度值。
拿示例3做个演示，题目所给:answerKey = “TTFTTFTT”, k = 1.
先考虑将F变成T的情况(即要找最长T的情况)。
- 假设左右指针都指向0下标元素，此时为T,右指针后移。
- 下标为1时也为T，右指针后移，下标为2时，变成F，计数器+1，但此时还未大于题目所给的k，所以继续后移。
- 但移动到下标为5时，为F，计数器变成2，已经大于k了。
- 这时将左指针向后移动，由0变成1，此时左指针所指依旧为T，并没有使得计数器小于k，继续后移。
- 直到移动到下标为2指向了F，此时计数器减1，计数器变成1，等于k，再将左指针向后挪一个，让他指向下标为3的数(实际上就是略过了一个F，让窗口间的F的个数始终保持等于k)。
重复上述步骤并在期间记录窗口长度最大值，并且还要考虑将F变成T的情况。取两者最大值即可。
这种方法就是要考虑T变F和F变T的两种情况，这两种情况可以融合放在一起统计，我懒得写了，情况分开思路比较好理解，就用这个吧。
完整代码
class Solution:def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:def a(answerKey,k,ch):i = 0j = 0temp = 0res = 0while j < len(answerKey):# 统计要变的那个字符的个数if answerKey[j] == ch:temp +=1# 超出可变个数while temp > k:# 不断移动左指针直到窗口内的值在允许范围内if answerKey[i] == ch:temp -=1i +=1res = max(res,j-i+1)j +=1print(res)return res# 判断两种情况，取最大的。res = max(a(answerKey,k,'T'),a(answerKey,k,'F'))return res