本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。一位老师正在出一场由n道判断题构成的考试每道题的答案为 true 用T表示或者 false 用F表示。老师想增加学生对自己做出答案的不确定性方法是最大化有连续相同结果的题数。也就是连续出现 true 或者连续出现 false。给你一个字符串answerKey其中answerKey[i]是第i个问题的正确结果。除此以外还给你一个整数k表示你能进行以下操作的最多次数每次操作中将问题的正确答案改为T或者F也就是将answerKey[i]改为T或者F。请你返回在不超过k次操作的情况下最大连续T或者F的数目。示例 1输入answerKeyTTFF,k2输出4解释我们可以将两个 ‘F’ 都变为 ‘T’ 得到 answerKey “TTTT” 。总共有四个连续的 ‘T’ 。示例 2输入answerKeyTFFT,k1输出3解释我们可以将最前面的 ‘T’ 换成 ‘F’ 得到 answerKey “FFFT” 。或者我们可以将第二个 ‘T’ 换成 ‘F’ 得到 answerKey “TFFF” 。两种情况下都有三个连续的 ‘F’ 。示例 3输入answerKeyTTFTTFTT,k1输出5解释我们可以将第一个 ‘F’ 换成 ‘T’ 得到 answerKey “TTTTTFTT” 。或者我们可以将第二个 ‘F’ 换成 ‘T’ 得到 answerKey “TTFTTTTT” 。两种情况下都有五个连续的 ‘T’ 。提示n answerKey.length1 n 5 * 10^4answerKey[i]要么是T要么是F1 k n解法 不定长滑窗求最长但越短越容易合法求a n s w e r K e y answerKeyanswerKey的一个最长子串包含至多k kk个T \text{T}T或者至多k kk个F \text{F}F。由于子串越长越无法满足要求有单调性可以用滑动窗口解决。遍历a n s w e r K e y answerKeyanswerKey枚举子串右端点r i g h t rightright同时维护最小左端点l e f t leftleft以及子串中的字符个数c n t cntcnt。把a n s w e r K e y [ r i g h t ] answerKey[right]answerKey[right]的出现次数加一。如果T \text{T}T和F \text{F}F的出现次数都超过k kk那么必须不断移动左端点l e f t leftleft同时减少a n s w e r K e y [ l e f t ] answerKey[left]answerKey[left]的出现次数直到T \text{T}T和F \text{F}F的出现次数至少有一个≤ k ≤k≤k。循环结束后说明子串右端点在r i g h t rightright时对应的最小左端点为l e f t leftleft用子串长度r i g h t − l e f t 1 right−left1right−left1更新答案的最大值。遍历a n s w e r K e y answerKeyanswerKey结束后返回答案。代码实现时由于T \text{T}T和F \text{F}F的 ASCII 值除以 2 后的奇偶性不同也就是它们二进制的次低位不同可以改为统计二进制次低位。classSolution{publicintmaxConsecutiveAnswers(StringanswerKey,intk){char[]sanswerKey.toCharArray();intans0;intleft0;int[]cntnewint[2];for(intright0;rights.length;right){cnt[s[right]11];while(cnt[0]kcnt[1]k){cnt[s[left]11]--;left;}ansMath.max(ans,right-left1);}returnans;}}classSolution{public:intmaxConsecutiveAnswers(string answerKey,intk){intans0,left0,cnt[2]{};for(intright0;rightanswerKey.length();right){cnt[answerKey[right]11];while(cnt[0]kcnt[1]k){cnt[answerKey[left]11]--;left;}ansmax(ans,right-left1);}returnans;}};classSolution:defmaxConsecutiveAnswers(self,answerKey:str,k:int)-int:ansleft0cntdefaultdict(int)forright,chinenumerate(answerKey):cnt[ch]1whilecnt[T]kandcnt[F]k:cnt[answerKey[left]]-1left1ansmax(ans,right-left1)returnansfuncmaxConsecutiveAnswers(answerKeystring,kint)(ansint){cnt:[2]int{}left:0forright,ch:rangeanswerKey{cnt[ch11]forcnt[0]kcnt[1]k{cnt[answerKey[left]11]--left}ansmax(ans,right-left1)}return}implSolution{pubfnmax_consecutive_answers(answer_key:String,k:i32)-i32{letsanswer_key.as_bytes();letmutans0;letmutleft0;letmutcnt[0,0];for(right,ch)ins.iter().enumerate(){cnt[(ch11)asusize]1;whilecnt[0]kcnt[1]k{cnt[(s[left]11)asusize]-1;left1;}ansans.max(right-left1);}ansas_}}varmaxConsecutiveAnswersfunction(answerKey,k){letans0,left0;constcnt{T:0,F:0};for(letright0;rightanswerKey.length;right){cnt[answerKey[right]];while(cnt[T]kcnt[F]k){cnt[answerKey[left]]--;left}ansMath.max(ans,right-left1);}returnans;};// 写法2varmaxConsecutiveAnswersfunction(answerKey,k){letans0,left0;constcnt[0,0];for(letright0;rightanswerKey.length;right){cnt[answerKey[right].charCodeAt(0)11];while(cnt[0]kcnt[1]k){cnt[answerKey[left].charCodeAt(0)11]--;left;}ansMath.max(ans,right-left1);}returnans;};#defineMAX(a,b)((b)(a)?(b):(a))intmaxConsecutiveAnswers(char*answerKey,intk){intans0,left0,cnt[2]{};for(intright0;answerKey[right];right){cnt[answerKey[right]11];while(cnt[0]kcnt[1]k){cnt[answerKey[left]11]--;left;}ansMAX(ans,right-left1);}returnans;}复杂度分析时间复杂度O ( n ) O(n)O(n)。空间复杂度O ( n ) O(n)O(n)。思考题把子串改为子序列该怎么做