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

2024-09-07 23:36

本文主要是介绍【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'));    }
};

~希望对你有启发!~

这篇关于【leetcode详解】考试的最大困扰度(滑动窗口典例)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146481

相关文章

Java异常架构Exception(异常)详解

《Java异常架构Exception(异常)详解》:本文主要介绍Java异常架构Exception(异常),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. Exception 类的概述Exception的分类2. 受检异常(Checked Exception)

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

Python GUI框架中的PyQt详解

《PythonGUI框架中的PyQt详解》PyQt是Python语言中最强大且广泛应用的GUI框架之一,基于Qt库的Python绑定实现,本文将深入解析PyQt的核心模块,并通过代码示例展示其应用场... 目录一、PyQt核心模块概览二、核心模块详解与示例1. QtCore - 核心基础模块2. QtWid

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键(Hot Key)定义特点应对策略示例数据倾斜(Data S

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Python实现Microsoft Office自动化的几种方式及对比详解

《Python实现MicrosoftOffice自动化的几种方式及对比详解》办公自动化是指利用现代化设备和技术,代替办公人员的部分手动或重复性业务活动,优质而高效地处理办公事务,实现对信息的高效利用... 目录一、基于COM接口的自动化(pywin32)二、独立文件操作库1. Word处理(python-d

JavaScript Array.from及其相关用法详解(示例演示)

《JavaScriptArray.from及其相关用法详解(示例演示)》Array.from方法是ES6引入的一个静态方法,用于从类数组对象或可迭代对象创建一个新的数组实例,本文将详细介绍Array... 目录一、Array.from 方法概述1. 方法介绍2. 示例演示二、结合实际场景的使用1. 初始化二

C#中的 StreamReader/StreamWriter 使用示例详解

《C#中的StreamReader/StreamWriter使用示例详解》在C#开发中,StreamReader和StreamWriter是处理文本文件的核心类,属于System.IO命名空间,本... 目录前言一、什么是 StreamReader 和 StreamWriter?1. 定义2. 特点3. 用

css中的 vertical-align与line-height作用详解

《css中的vertical-align与line-height作用详解》:本文主要介绍了CSS中的`vertical-align`和`line-height`属性,包括它们的作用、适用元素、属性值、常见使用场景、常见问题及解决方案,详细内容请阅读本文,希望能对你有所帮助... 目录vertical-ali