LC2024.考试的最大困扰

思路1：贪心算法

• 一段区间内部，要是刚好有个T，那么就把所有的T统统变成F，那么这一段区间就是一段连续的FFF...FFF序列了。如果能把所有的“有个T的区间”全部进行这样的操作，那么就可以得到最好的结果了。
• 具体的做法如下，listT[i]表示第个出现的T的下标，那么第个T出现的位置，减去第个T出现的位置，得到的区间就是我们希望的“有个T的区间”。
• 但是害怕一种情况的出现，就是形如FFFFFTTT and k = 3这样的情况，这样的话第0个T所在的位置太靠后了，前面那么多个F算不到里面去了，所以，在listT[i]中预先加上，等于在AnswerKey中位置预先隐藏一个字符，这样计算listT[i + k] - listT[i - 1] - 1就能计算出完整情况了。

  代码1：

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        # 贪心算法去做一次扫描估计是不行的，里面重复的情况太复杂了
        # 考虑另外一种贪心算法
        listT, listF = [-1], [-1]
        lenAnswerKey = len(answerKey)
        for i in range(lenAnswerKey):
            if answerKey[i] == 'T':
                # 存放出现位置的下标
                listT.append(i)
            else:
                listF.append(i)
        # 认为最后增加一个位置是二者中的任意一个
        listT.append(lenAnswerKey)
        listF.append(lenAnswerKey)
        if k >= len(listT) - 2 or k >= len(listF) - 2:
            return lenAnswerKey
        res = 0
        i = 1
        # 实际上在算F序列的大小
        while i + k < len(listT):
            res = max(res, listT[i + k] - listT[i - 1] - 1)
            i += 1
        i = 1
        while i + k < len(listF):
            res = max(res, listF[i + k] - listF[i - 1] - 1)
            i += 1
        return res

思路2：滑动窗口

• 基本的思路也用到了贪心的思想：如果某个区间内有个F，那么把个F全部变成T，就可以得到一组最长的区间。现在的任务变成了如何找到符合这一条件的区间。
• 利用滑动窗口的思想，如果符合要求就往右走，不符合要求就重复弹出左边的元素。直到满足要求为止。

• right += 1靠后写，不然计算maxLen = max(maxLen, right - left + 1)会多算。

  代码2：

  class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        # 滑动窗口
        # 如果没有满k个F，就继续扫，如果满k个F了，就放弃掉最左边的数字
        def scanMax(ch: str):
            left, right = 0, 0
            maxLen, countK = 0, 0
            while right < len(answerKey):
                countK += (1 if answerKey[right] == ch else 0)
                while countK > k:
                    countK -= (1 if answerKey[left] == ch else 0)
                    left += 1
                maxLen = max(maxLen, right - left + 1)
                # 写在后面，不然会多加
                right += 1
            return maxLen
        return max(scanMax('T'), scanMax('F'))

  思路3：二分查找

• 采用类似前缀和的方法进行计数，cnt[i]表示长度为len的字符串中，‘T’出现的次数。

• 利用二分查找代替暴力搜索，如果T或者F出现的次数小于等于k，那么这个子字符串一定是符合的，然后通过长度去遍历，得到满足条件的最长长度即可。

  代码：

  class Solution {
  public:
    int judge(int len, vector<int> cnt, int n, int k) {
        // i需要从0开始，如果从1开始会忽略掉第一个
        for (int i = 0; i + len <= n; i++) {
            int cur_t = cnt[i + len] - cnt[i];
            if (min(cur_t, len - cur_t) <= k) {
                return true;
            }
        }
        return false;
    }
    int maxConsecutiveAnswers(string answerKey, int k) {
        int n = answerKey.size();
        vector<int> cnt(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            // cnt[i]长度为i的数组中T出现的频率
            cnt[i] = cnt[i - 1] + (answerKey[i - 1] == 'T' ? 1 : 0);
        }
        int left = 1, right = n; 
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (judge(mid, cnt, n, k)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
  };