本文涉及的基础知识点

C++二分查找
C++算法：滑动窗口总结

LeetCode2024. 考试的最大困扰度

一位老师正在出一场由 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’ 。

提示：
n == answerKey.length
1 <= n <= 5 * 10⁴
answerKey[i] 要么是 ‘T’ ，要么是 ‘F’
1 <= k <= n

二分查找

二分类型：寻找末端
Check函数参数范围：[1,n]
Check函数：
长度为mid的滑动窗口，cnt记录T的数量，则F的数量cnt1 = mid - cnt。任何滑动窗口cnt或cnt1的数量大于等于mid-k就返回true。否则返回false。

代码

核心代码

template<class INDEX_TYPE>
class CBinarySearch
{
public:
	CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}
	template<class _Pr>
	INDEX_TYPE FindFrist( _Pr pr)
	{
		auto left = m_iMin - 1;
		auto rightInclue = m_iMax;
		while (rightInclue - left > 1)
		{
			const auto mid = left + (rightInclue - left) / 2;
			if (pr(mid))
			{
				rightInclue = mid;
			}
			else
			{
				left = mid;
			}
		}
		return rightInclue;
	}
	template<class _Pr>
	INDEX_TYPE FindEnd( _Pr pr)
	{
		int leftInclude = m_iMin;
		int right = m_iMax + 1;
		while (right - leftInclude > 1)
		{
			const auto mid = leftInclude + (right - leftInclude) / 2;
			if (pr(mid))
			{
				leftInclude = mid;
			}
			else
			{
				right = mid;
			}
		}
		return leftInclude;
	}
protected:
	const INDEX_TYPE m_iMin, m_iMax;
};

	class Solution {
		public:
			int maxConsecutiveAnswers(string answerKey, int k) {
				auto Check = [&](int mid) {
					int cnt = 0;
					int i=0;
					const int need = mid - k;
					for (; i < mid; i++) {
						if ('T' == answerKey[i]) { cnt++; }
					}
					if ((cnt >= need) || (mid - cnt) >= need) { return true; }
					for (; i < answerKey.length(); i++) {
						if ('T' == answerKey[i]) { cnt++; }
						if ('T' == answerKey[i - mid]) { cnt--; }
						if ((cnt >= need) || (mid - cnt) >= need) { return true; }
					}
					return false;
				};
				return CBinarySearch<int>(1, answerKey.length()).FindEnd(Check);
			}
		};

	

单元测试

string answerKey; int k;
		TEST_METHOD(TestMethod11)
		{
			answerKey = "TTFF", k = 2;
			auto res = Solution().maxConsecutiveAnswers(answerKey, k);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			answerKey = "TFFT", k = 1;
			auto res = Solution().maxConsecutiveAnswers(answerKey, k);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			answerKey = "TTFTTFTT", k = 1;
			auto res = Solution().maxConsecutiveAnswers(answerKey, k);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod14)
		{
			answerKey = "FFTFTTTFFTTTTFTTFFTFTTFTFTTFFFTTTTFFFTFFFFTTFTFTTFFFFTFTFTFTTFFTFFTFFFFFFTTFFTFFTFFTFFFFFTFTTFFTTFTT", k = 10;
			auto res = Solution().maxConsecutiveAnswers(answerKey, k);
			AssertEx(34, res);
		}