LeedCode刷题---滑动窗口问题

顾得泉:个人主页
个人专栏:《Linux操作系统》 《C/C++》 《LeedCode刷题》
键盘敲烂,年薪百万!
一、长度最小的子数组
题目链接:长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4] 输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1] 输出:0
提示:
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
解法
解法一(暴力求解)(会超时):
算法思路:
「从前往后」枚举数组中的任意一个元素,把它当成起始位置。然后从这个「起始位置」开始,然后寻找一段最短的区间,使得这段区间的和「大于等于」目标值。将所有元素作为起始位置所得的结果中,找到「最小值」即可。
解法二(滑动窗口):
算法思路:
由于此问题分析的对象是一段连续的区间,因此可以考虑「滑动窗口」的思想来解决这道题。让滑动窗口满定:从i位置开始,窗口内所有元素的和小于target(那么当窗口内元素之和第一次大于等于国标值的时候,就是i位置开始,满足条件的最小长度)。
做法:
将右端元素划入窗口中,统计出此时窗口内元素的和:
如果窗口内元素之和大于等于target:更新结果,并且将左端元素划出去的同时继续判断是否满足条件并更新结果(因为左端元素可能很小,划出去之后依旧满足条件)
如果窗口内元素之和不满足条件: right++,另下一个元素进入窗口。
为何滑动窗口可以解决问题,并且时间复杂度更低?
这个窗口寻找的是:以当前窗口最左侧元素(记为left1)为基准,符合条件的情况。也就是在这道题中,从left1开始,满足区间和sum >= target时的最右侧((记为right1))能到哪里。
我们既然已经找到从left1开始的最优的区间,那么就可以大胆舍去left1。但是如果继续像方法一样,重新开始统计第二个元素(left2)往后的和,势必会有大量重复的计算(因为我们在求第一段区间的时候,已经算出很多元素的和了,这些和是可以在计算下次区间和的时候用上的)。
此时,rigth1的作用就体现出来了,我们只需将left1这个值从sum中剔除。从right1这个元素开始,往后找满足left2元素的区间(此时ight也有可能是满足的,因为left1可能很小。sum剔除掉left1之后,依旧满定大于等于target )。这样我们就能省掉大量重复的计算。
这样我们不仅能解决问题,而且效率也会大大提升。
时间复杂度:虽然代码是两层循环,但是我们的left 指针和right指针都是不回退的,两者最多都往后移动n次。因此时间复杂度是o(N)。
代码实现
class Solution
{
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(), sum = 0, len = INT_MAX;for(int left = 0, right = 0; right < n; right++){sum += nums[right];while(sum >= target){len = min(len, right - left + 1);sum -= nums[left];left++;}}return len == INT_MAX ? 0 : len;}
};
二、无重复字符的最长字串
题目链接:无重复字符的最长子串
题目描述
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc" 所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b" 所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke"是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
解法
算法思路:
研究的对象依旧是一段连续的区间,因此继续使用「滑动窗口」思想来优化。让滑动窗口满足:窗口内所有元素都是不重复的。
做法:
右端元素ch进入茵口的时候,哈希表统计这个字符的频次:
如果这个字符出现的频次超过1,说明窗口内有重复元素,那么就从左侧开始划出窗口,直到ch这个元素的频次变为1,然后再更新结果。
如果没有超过1,说明当前窗口没有重复元素,可以直接更新结果
代码实现
class Solution
{
public:int lengthOfLongestSubstring(string s) {int hash[123] = {0};int left = 0, right = 0, ret = 0, n = s.size();while(right < n){hash[s[right]]++;while(hash[s[right]] > 1)hash[s[left++]]--;ret = max(ret , right - left + 1);right++;}return ret;}
};
三、最大连续1的个数Ⅲ
题目链接:最大连续1的个数 III
题目描述
给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。
示例 1:
输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出:6 解释:[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1,最长的子数组长度为 6
示例 2:
输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出:10 解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1,最长的子数组长度为 10
提示:
1 <= nums.length <= 105nums[i]不是0就是10 <= k <= nums.length
解法
算法思路:
不要去想怎么翻转,不要把问题想的很复杂,这道题的结果就是一段连续的1中间塞了k个0。
因此,我们可以把问题转化成:求数组中一段最长的连续区间,要求这段区间内的0个数不超过k个。
既然是连续区间,可以考虑使用「滑动窗口」来解决问题。
算法流程:
a.初始化一个大小为2的数组就可以当做哈希表hash 了;初始化一些变量left = 0,right = 0 , ret = 0;
b.当right小于数组大小的时候,一直下列循环:
i.让当前元素进入窗口,顺便统计到哈希表中;
ii.检查0的个数是否超标:
如果超标,依次让左侧元素滑出窗口,顺便更新哈希表的值,直到的个数恢复正常;
iii.程序到这里,说明窗口内元素是符合要求的,更新结果;iv. right++,处理下一个元素;
c.循环结束后,ret存的就是最终结果。
代码实现
class Solution
{
public:int longestOnes(vector<int>& nums, int k) {int ret = 0;for(int left = 0, right = 0, zero = 0; right < nums.size(); right++){if(nums[right] == 0) zero++; while(zero > k) if(nums[left++] == 0) zero--; ret = max(ret, right - left + 1); }return ret;}
};
结语:今日的刷题分享到这里就结束了,希望本篇文章的分享会对大家的学习带来些许帮助,如果大家有什么问题,欢迎大家在评论区留言~~~
相关文章:
LeedCode刷题---滑动窗口问题
顾得泉:个人主页 个人专栏:《Linux操作系统》 《C/C》 《LeedCode刷题》 键盘敲烂,年薪百万! 一、长度最小的子数组 题目链接:长度最小的子数组 题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。…...
leetcode24. 两两交换链表中的节点
题目描述 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 示例 1: 输入:head [1,2,3,4] 输出&#…...
TCP传输层详解(计算机网络复习)
介绍:TCP/IP包含了一系列的协议,也叫TCP/IP协议族,简称TCP/IP。该协议族提供了点对点的连接机制,并将传输数据帧的封装、寻址、传输、路由以及接收方式都予以标准化 TCP/IP的分层模型 在讲TCP/IP协议之前,首先介绍一…...
【LuatOS】简单案例网页点灯
材料 硬件:合宙ESP32C3简约版,BH1750光照度模块,0.96寸OLED(4P_IIC),杜邦线若干 接线: ESP32C3.GND — OLED.GND — BH1750.GND ESP32C3.3.3V — OLED.VCC — BH1750.VCC ESP32C3.GPIO5 — OLED.SCL — BH1750.SCL E…...
百度APP iOS端包体积50M优化实践(七)编译器优化
一. 前言 百度APP iOS端包体积优化系列文章的前六篇重点介绍了包体积优化整体方案、图片优化、资源优化、代码优化、无用类优化、HEIC图片优化实践和无用方法清理,图片优化是从无用图片、Asset Catalog和HEIC格式三个角度做深度优化;资源优化包括大资源…...
STM32-新建工程(标准库)
目录 STM32F10x新建工程(标准库) 移植文件夹 新建工程 添加启动文件和必需文件 在工程中加载新添加的文件 在工程中添加文件路径 在工程中添加main函数 添加lib库 添加必需文件 添加宏定义 点亮LED(标准库) STM32F10x新…...
Android集成科大讯飞语音识别与语音唤醒简易封装
目录 一、语音唤醒部分 1、首先在科大讯飞官网注册开发者账号 2、配置唤醒词然后下载sdk 3、选择对应功能下载 4、语音唤醒lib包全部复制到工程目录下 5、把语音唤醒词文件复制到工程的assets目录 6、复制对应权限到AndroidManifest.xml中 7、唤醒工具类封装 二、语音识…...
【Linux】telnet命令使用
telnet命令 telnet命令用于使用telnet协议与另一台主机进行通信。如果在没有主机参数的情况下调用telnet,它将进入命令模式,由其提示(telnet>)指示。在这种模式下,它接受并执行下面列出的命令。如果使用参数调用它…...
VCG 标记使用(BitFlags)
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 对于网格的每个单形,我们都有一个称为BitFlags的组件,该组件存储固定大小的32位向量,用于各种需求。管理这些标志的相关类:vcg::tri::UpdateFlags与vcg::tri::UpdateSelection。主要的标记有:删除标记、边界标记…...
Pandas中的Series(第1讲)
Pandas中的Series(第1讲) 🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔…...
从手工测试进阶中高级测试?如何突破职业瓶颈...
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 1、手工测试如何进…...
【链表Linked List】力扣-114 二叉树展开为链表
目录 题目描述 解题过程 官方题解 题目描述 给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。展开后的单链表应…...
Go (一) 基础部分4 -- 文件处理
一、文件基本介绍 1.1、打开一个文件 基本介绍:打开一个文件用于读取,如果操作成功,返回的文件对象的方法可用于读取文件数据。如果出错,错误底层类型是"*.PathError" func Open(name string) (*File, error) name stri…...
集合03 Collection (List) - Java
List ArrayListArrayList注意事项ArrayList底层操作机制-源码分析(重点) VectorVector基本介绍 ——Vector和ArrayList比较Vector底层结构和源码分析 LinkedList基本介绍LinkedList的底层结构和操作机制LinkedList的增删改查 ——LinkedList和ArrayList比…...
国产化软件突围!怿星科技eStation产品荣获2023铃轩奖“前瞻优秀奖”
11月11日,2023中国汽车供应链峰会暨第八届铃轩奖颁奖典礼在江苏省昆山市举行。怿星科技凭借eStation产品,荣获2023铃轩奖“前瞻智能座舱类优秀奖”,怿星CEO潘凯受邀出席铃轩奖晚会并代表领奖。 2023铃轩奖“前瞻智能座舱类优秀奖” 铃轩奖&a…...
如何解决Redis热Key问题?
Redis热点key是指访问频率较高的key,当大量的请求集中在一个或少数几个热点key上时,会导致这些key所在的Redis节点的CPU、内存和网络带宽等资源被大量消耗,影响Redis集群的整体性能和稳定性。 热点Key带来的问题 Redis节点负载过高࿱…...
react Hooks之useId
当我们在编写React组件时,有时需要为元素生成唯一的ID。这种情况经常出现在表单元素、标签和用于无障碍性的目的上。React提供了一个名为useId的自定义Hook,它可以帮助我们生成唯一的ID。 1、作用: 用于生成一个唯一的 ID。这个 ID 可以用于…...
2023年全球软件开发大会(QCon广州站2023)-核心PPT资料下载
一、峰会简介 本次峰会包含:泛娱乐时代的边缘计算与通讯、稳定性即生命线、下一代软件架构、出海的思考、现代数据架构、AGI 与 AIGC 落地、大前端技术探索、编程语言实战、DevOps vs 平台工程、新型数据库、AIGC 浪潮下的企业出海、AIGC 浪潮下的效能智能化、数据…...
MicroSD 卡 使用读卡器 读取速度测试
设备 - - 电脑为m.2固态硬盘 usb口为USB3.2 gen2接口(即支持1GB/s的接口) cpu: amd3600 测试方案1 直接MicroSD卡放入读卡器测试 38MB/s 从sd卡复制到本地C盘 测试方案2 MicroSD卡使用闪迪的SD卡套套上之后一起插入读卡器 76MB/s 从sd卡复制到本地C盘...
Selenium+Unittest+HTMLTestRunner框架更改为Selenium+Pytest+Allure(一)
背景:之前的框架,Selenium是3.x版本,现在更新到4.15版本后,一些写法如find_element_by_xxx 不再支持,改为find_element(By.xxx)的方式,同时由于Unittest不如Pytest在执行方面灵活(比如只执行冒烟…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果,支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...
