### 题目描述 一位老师正在出一场由 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 = "TFFT", k = 1 输出：3 解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。 或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。 两种情况下，都有三个连续的 'F' 。 ``` ### 题目解答 #### 思路 我们考虑2种情况，一种是将F转换成T，获得尽可能多连在一起的T；第二种是将T转成F,获得尽可能多连在一起的F。 在此过程中，采用滑动窗口的方式，在窗口中保存转换成符合条件的字符。如果转化次数小于k，那么如果不符合条件就将其转换，如果符合条件就直接将其加入滑动窗口。如果转换次数为0，那么从左侧开始收缩滑动窗口，判断其本身是转换的，还是本身就符合条件的字符。 **算法复杂度** 时间复杂度：采用滑动窗口，从左到右每个字符遍历一次，因此时间复杂度是$$O(n)$$ 空间复杂度：需要几个变量，记录滑动窗口边界，反转次数等，因此空间复杂度是$$O(1)$$ #### 代码实现 ```python class Solution: def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int: def count_max(c): left = 0 right = 0 max_t = 0 turn = 0 # 假设区间内使得T最大 while right < len(answerKey): if answerKey[right] == c: right += 1 else: if turn < k: turn += 1 right += 1 else: if answerKey[left] != c: turn -= 1 left += 1 max_t = max(right - left, max_t) return max_t return max(count_max('T'), count_max('F')) ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复