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在执行方面灵活(比如只执行冒烟…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果