【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数

本文主要是介绍【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【LeetCode刷题】Day 8

  • 题目1:1004.最大连续1的个数 III
    • 思路分析:
    • 思路1:暴力枚举+zero计数器
    • 思路2:滑动窗口+zero计数器
  • 题目2:1658. 将x减到0的最小操作数
    • 思路分析:
    • 思路1:暴力枚举
    • 思路2:滑动窗口O(N)
  • 收获满满✨:

在这里插入图片描述

题目1:1004.最大连续1的个数 III

在这里插入图片描述

思路分析:

如果我们根据题干意思来做,每次寻找并翻转k个0的话,难度还是比较大,很复杂。我们不妨使用zero计数器来控制0的数量,控制在k以内。

思路1:暴力枚举+zero计数器

思路2:滑动窗口+zero计数器

本题滑动窗口分析:
1. 进窗口:nums[right]!=0或者zero小于k,就进窗口,执行 right++。意思就是right++就代表符合题意。
2. 判断: 主要目的是更新 left到符合题干的位置,即: 减去一个零,使得zero计数器为k的位置。更新到位置也就完成了 出窗口
3. 更新结果: ret是满足一个就更新一次,进窗口就是增加,出窗口就是减小(所以要和之前的比对,取最大)。

代码实现:

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left=0,right=0,n=nums.size();int zero=0,ret=0;while(right<n){if(nums[right]==0) zero++; //zero计数器while(zero>k)           //出窗口if(nums[left++]==0) zero--;ret=max(ret,right-left+1);//更新结果right++;				//符合要求进窗口-->right++;}return ret;}
};

LeetCode链接:1004.最大连续1的个数


题目2:1658. 将x减到0的最小操作数

在这里插入图片描述

思路分析:

一会左删一会右删,让删除的总数等于x,这道题我们直接做会很难。
不妨正难则反:中间的部分的和一直是:sum-x,要求删除最少,那就是中间长度最长。这样题目要求就变成了:找子数组的和等于target=sum-x的最长子数组。

思路1:暴力枚举

思路2:滑动窗口O(N)

本题滑动窗口分析:
1. 进窗口: 维护数据 sum1right++进窗口。
2. 判断: 如果 sum1>target,则需要出窗口来减少 sum1。出窗口操作: sum1-=nums[left++];
3. 更新结果: 需要满足条件再更新结果: if(sum1==target) ret=max(ret,right-left+1);
代码实现:
class Solution {
public:int minOperations(vector<int>& nums, int x) {int left=0,right=0,n=nums.size();int sum=0,sum1=0,ret=-1;、//求和for(int i=0;i<n;i++)sum += nums[i];int target=sum-x;//细节处理:if(target<0) return -1;while(right<n){sum1+=nums[right];              //进窗口while(sum1>target)              //判断sum1-=nums[left++];         //出窗口if(sum1==target)ret=max(ret,right-left+1);  //更新结果right++;}return (ret==-1?ret:n-ret);}
};

LeetCode链接:1658. 将x减到0的最小操作数


收获满满✨:

  • 正难则反,这个往往是最难的,需要多多体会。
  • 体会进窗口和出窗口,理解方式多样。

懒猫配果汁,美好周末!🎈🎈周末快乐~
在这里插入图片描述


这篇关于【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1005737

相关文章

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

解决Entity Framework中自增主键的问题

《解决EntityFramework中自增主键的问题》:本文主要介绍解决EntityFramework中自增主键的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录Entity Framework中自增主键问题解决办法1解决办法2解决办法3总结Entity Fram

Nginx 配置跨域的实现及常见问题解决

《Nginx配置跨域的实现及常见问题解决》本文主要介绍了Nginx配置跨域的实现及常见问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来... 目录1. 跨域1.1 同源策略1.2 跨域资源共享(CORS)2. Nginx 配置跨域的场景2.1

qt5cored.dll报错怎么解决? 电脑qt5cored.dll文件丢失修复技巧

《qt5cored.dll报错怎么解决?电脑qt5cored.dll文件丢失修复技巧》在进行软件安装或运行程序时,有时会遇到由于找不到qt5core.dll,无法继续执行代码,这个问题可能是由于该文... 遇到qt5cored.dll文件错误时,可能会导致基于 Qt 开发的应用程序无法正常运行或启动。这种错