【leetcode详解】考试的最大困扰度（滑动窗口典例）

本文主要是介绍【leetcode详解】考试的最大困扰度（滑动窗口典例），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实战总结：

sum += answerKey[right] == c; 经典操作，将判断语句转化为0， 1接收来计数
//大问题分解: 对'T'还是'F'做修改, 传参为c
//滑动窗口: 遍历, 维护left& right指向及 c的个数, 更新
不知从何下手写代码时：考虑先写好第一次的，然后以此为基础补充代码以适后续情况

题面：

解题感受： 思路总体好想，实现略有挑战。

思路分析：

//rt不断向右遍历
//sum由rt,lf分别更新,记录二者所夹区间内的情况
//遍历情况用0,1记录在sum中,作为更新lf的参考
//每一次循环都更新一次mx,保证不重不漏//这一步减少了太多分类讨论操作，详见文末代码

代码实现：

class Solution{
public:int maxConsecutiveAnswers(string answerKey, int k){//大问题分解: 对'T'还是'F'做修改, 传参为c//滑动窗口: 遍历, 维护left& right指向 及 c的个数, 更新int len = answerKey.length(); auto getcnt = [&](char c) -> int{int mx = 0;//rt不断向右遍历//sum由rt,lf分别更新,记录二者所夹区间内的情况//遍历情况用0,1记录在sum中,作为更新lf的参考//每一次循环都更新一次mx,保证不重不漏for(int lf=0, rt=0, sum=0; rt<len; rt++ ){//先写好第一次的sum += answerKey[rt] == c;//再补上后面的更新操作while(sum > k)//一直找到第k+1个{			  //以sum为依据,更新lf的值sum -= answerKey[lf++] == c;}mx = max(mx, rt-lf+1);//每一次循环都做一次更新,就避免了繁琐的分类讨论}return mx;			};return max(getcnt('F'), getcnt('T'));}
};

可以对比：由于最初没有想到每次循环时都要更新mx值，而修补出的含大量分类讨论的代码：（甚至最后依然不能AC）

class Solution {
public:int maxConsecutiveAnswers(string answerKey, int k) {auto getcnt = [&](char c) -> int{int pre = 0, mx = 0, cnt = 1, len = answerKey.length();int i=0;while(answerKey[i] != c && i < len) i++;if(answerKey[0] != c) pre = 0;else pre = i;//?// cout<<"t1 ";			if(i == len) return len;int j=i+1;//记忆化?while(cnt <= k && j < len){if(answerKey[j] == c) cnt++;j++;}if(j == len) return len;mx = max(mx, j-pre+1-1);while(j < len){mx = max(mx, j-pre+1);i++, j++;pre = i;while(answerKey[i] != c && i < len) i++;
//				cout<<"t4 ";while(j < len && answerKey[j] != c) j++;
//				cout<<"t5 ";}return mx;};return max(getcnt('T'), getcnt('F'));    }
};