当前位置: 首页 > news >正文

C++算法——滑动窗口

一、长度最小的子数组

1.链接

209. 长度最小的子数组 - 力扣(LeetCode)

2.描述

3.思路

本题从暴力求解的方式去切入,逐步优化成“滑动窗口”,首先,暴力枚举出各种组合的话,我们先让一个指针指向第一个,然后往后逐一遍历区间,也就是穷举出所有的子数组,但根据题目要求,当我们穷举出大于或者等于target的区间时,右边指针再向后遍历穷举的结果将没有意义,所以不需要再去往后走,而是进行下一轮遍历(前提是本题中数据全是正整数),当左指针往后走一步后,穷举的思路需要我们从头再走一次重复的数据,此时我们对其进行优化,定义一个sum值去记录区间数据,就可以不需要再次遍历一次,经过优化后,我们会发现,解题思路就变成了:

定义两个左右指针,一起从头往前走,并且记录两个指针区间的和sum,right指针往后,当大于等于目标值时,则停下记录长度,然后left走一步,进行判断是否仍然满足大于等于目标值,若是满足则让left继续走,当长度出现比原先短的区间时,进行更新最小区间的长度,left走到小于目标值时,让right进行往前走,直到right遍历完一遍数组,这种两个指针同向一起走的思路叫做“滑动窗口”

4.参考代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0;int right = 0;int sum = nums[0];int len = 0;while(right < nums.size()){if(sum < target){++right;if(right < nums.size())sum+=nums[right];}else{len = len == 0 ? right-left+1 :  min(len,right - left + 1);if(len == 1) break;sum-=nums[left++];}}return len;}
};

二、无重复字符的最长子串

1.链接

3. 无重复字符的最长子串 - 力扣(LeetCode)

2.描述

3.思路

由于是对子串进行判断,子串是一段连续的区间,所以我们可以尝试采用滑动窗口的思路解决

满足窗口滑动的条件就是:判断窗口内是否有重复字符,可以利用哈希表去进行统计

当没有重复时则right往前走,当有重复时则left往前,这个过程中记录下最长的子串

4.参考代码

class Solution 
{
public:int lengthOfLongestSubstring(string s) {if(s.size() == 0){return 0;}int left = 0;int right = 0;int len = 0;set<char> hash;while(right < s.size()){if((hash.insert(s[right])).second)//插入成功意味着没有重复{right++;len = max(len,right-left);}else//出现重复{hash.erase(s[left++]);}}return len;}
};

三、最大连续1的个数|||

1.链接

1004. 最大连续1的个数 III - 力扣(LeetCode)

2.描述

3.思路

可以将题意转化为,在一段区间内,0的数量不能超过k个,利用滑动窗口去解决

当超过k个时,left往前走,直到将最前面的0给退出窗口,没有超过时,则right往前走,不断扩大窗口,过程中记录下窗口长度最大的值

4.参考代码

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0;int right= 0;int n = nums.size();int len = 0;while(right < n){while(right < n && (k != 0 || nums[right] == 1)){if(nums[right] == 0){k--;}right++;len = max(len,right-left);}while(left < n && k == 0){if(nums[left++] == 0)k++;}}return len;}
};

四、将x减到0的最小操作数

1.链接

1658. 将 x 减到 0 的最小操作数 - 力扣(LeetCode)

2.描述

3.思路

我们可以先将问题转换成,在数组内找到一段最长连续的子区间之和会刚好等于数组之和减去x的值

将问题变成在数组中找一段最长的连续子区间之和等于目标值的问题后,我们就可以使用滑动窗口的思路去解决,思路可以参考第一题“长度最小的子数组”

4.参考代码

class Solution 
{
public:int minOperations(vector<int>& nums, int x) {int n = nums.size();int sum = 0;for(auto n:nums){sum+=n;}int target = sum - x;if(target < 0) return -1;//找到最长的子区间int len = -1;for(int left = 0,right = 0,s = 0; right < n;right++ ){s += nums[right];//进窗口while(s > target)//出窗口{s-=nums[left++];}if(s == target){len = max(len,right-left+1);}}return len == -1 ? len : n-len;}
};

五、水果成篮

1.链接

904. 水果成篮 - 力扣(LeetCode)

2.描述

3.思路

根据题意,利用滑动窗口的思路,当窗口内的水果种类超过两种时则开始出窗口,过程中记录下窗口的长度,利用哈希表去进行统计

4.参考代码

class Solution {
public:int totalFruit(vector<int>& fruits) {map<int,int> hash;int ret = 0;for(int left = 0,right = 0;right<fruits.size();right++){hash[fruits[right]]++;while(hash.size()>2){hash[fruits[left]]--;if(hash[fruits[left]] == 0){hash.erase(fruits[left]);}left++;}ret = max(ret,right-left+1);}return ret;}
};

六、找到字符串中所有字母异位词

1.链接

438. 找到字符串中所有字母异位词 - 力扣(LeetCode)

2.描述

3.思路

4.参考代码

class Solution 
{
public:vector<int> findAnagrams(string s, string p) {int hash1[26] = {0};int hash2[26] = {0};for(auto c:p){hash1[c-'a']++;}int m = p.size();vector<int> ret;for(int left = 0,right = 0,count = 0; right < s.size(); right++){char in = s[right];hash2[in - 'a']++;//入窗口if(hash2[in - 'a'] <= hash1[in - 'a']) count++;//维护countchar out = s[left];if(right-left+1 > m)//出窗口{if(hash2[out - 'a'] <= hash1[out - 'a']) count--;//维护counthash2[out - 'a']--;left++;}//判断目标if(count == m){ret.push_back(left);}}return ret;}
};

七、串联所有单词的子串

1.链接

30. 串联所有单词的子串 - 力扣(LeetCode)

2.描述

3.思路

4.参考代码

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {int len = words[0].size();unordered_map<string,int> m1;unordered_map<string,int> m2;vector<int> ret;for(auto& s:words) m1[s]++;for(int i = 0;i<len;i++)//以i位置为起点{for(int left = i,right = i+len-1,count = 0; right < s.size() ; right+=len)//滑动窗口{string in = s.substr(right-len+1,len);m2[in]++;//入窗口if(m2[in] <= m1[in]) count++;//维护countif(right-left+1 > len*words.size())//出窗口{string out = s.substr(left,len);if(m2[out] <= m1[out]) count--;m2[out]--;left+=len;}if(count == words.size()) ret.push_back(left);}m2.clear();}return ret;}
};

八、最小覆盖子串

1.链接

76. 最小覆盖子串 - 力扣(LeetCode)

2.描述

3.思路

有了前面的经验,不难想到这题该怎么用滑动窗口解决,根据题意分析,我们知道首先将t内的字符记录到哈希表hash1中,然后让滑动窗口的右侧不断的往前走,直到满足题目条件,即滑动窗口内的字符串包含了t内的字符,此时让left往前收缩,记录下最小的区间,然后直到不再满足条件后,让right继续往后找满足条件的子串,最终记录下最短的那个子串即可,当然,还有如何优化哈希比较的细节需要注意,以及对于如何记录下最短子串的考量

4.参考代码

class Solution {
public:string minWindow(string s, string t) {int n = s.size();int hash1[128] = {0};int hash2[128] = {0};for(auto& c : t)  hash1[c]++;int begin = -1; int len = s.size()+1;for(int left = 0,right = 0,count = 0;right < n;right++){char in = s[right];hash2[in]++;if(hash2[in] <= hash1[in]) count++;while(count == t.size()){if(right-left+1 < len){len = right-left+1;begin = left;}char out = s[left++];if(hash2[out] <= hash1[out]) count--;hash2[out]--;}}if(begin == -1) return "";else return s.substr(begin,len);}
};

总结

本章节主要整理了关于滑动窗口的算法思想,由简单到困难逐步递进,整理了八道相关例题以及思路解析提供参考,也可以通过链接去做

相关文章:

C++算法——滑动窗口

一、长度最小的子数组 1.链接 209. 长度最小的子数组 - 力扣&#xff08;LeetCode&#xff09; 2.描述 3.思路 本题从暴力求解的方式去切入&#xff0c;逐步优化成“滑动窗口”&#xff0c;首先&#xff0c;暴力枚举出各种组合的话&#xff0c;我们先让一个指针指向第一个&…...

Rust---有关介绍

目录 Rust---有关介绍变量的操作Rust 数值库&#xff1a;num某些基础数据类型序列(Range)字符类型单元类型 发散函数表达式&#xff08;&#xff01; 语句&#xff09; Rust—有关介绍 得益于各种零开销抽象、深入到底层的优化潜力、优质的标准库和第三方库实现&#xff0c;Ru…...

vue项目双击from表单限制重复提交 添加全局注册自定义函数

第一步: 找到utils文件夹添加directive.js文件 import Vue from vue //全局防抖函数 // 在vue上挂载一个指量 preventReClick const preventReClick Vue.directive(preventReClick, {inserted: function (el, binding) {console.log(el.disabled)el.addEventListener(click,…...

WebPack的使用及属性配、打包资源

WebPack(静态模块打包工具)(webpack默认只识别js和json内容) WebPack的作用 把静态模块内容压缩、整合、转译等&#xff08;前端工程化&#xff09; 1️⃣把less/sass转成css代码 2️⃣把ES6降级成ES5 3️⃣支持多种模块文件类型&#xff0c;多种模块标准语法 export、export…...

机器学习实战17-高斯朴素贝叶斯(GaussianNB)模型的实际应用,结合生活中的生动例子帮助大家理解

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下机器学习实战17-高斯朴素贝叶斯(GaussianNB)模型的实际应用&#xff0c;结合生活中的生动例子帮助大家理解。GaussianNB&#xff0c;即高斯朴素贝叶斯模型&#xff0c;是一种基于概率论的分类算法&#xff0c;广泛应…...

数据处理库Pandas数据结构DataFrame

Dataframe是一种二维数据结构&#xff0c;数据以表格形式&#xff08;与Excel类似&#xff09;存储&#xff0c;有对应的行和列&#xff0c;如图3-3所示。它的每列可以是不同的值类型&#xff08;不像 ndarray 只能有一个 dtype&#xff09;。基本上可以把 DataFrame 看成是共享…...

中国发展新能源的核心驱动力是什么?其原理是如何运作的?

中国发展新能源的核心驱动力是推进能源消费方式变革、构建多元清洁能源供应体系、实施创新驱动发展战略、深化能源体制改革和持续推进国际合作。 新能源的发展背后有多重经济、政策及环境因素的推动&#xff1a; 经济发展需求&#xff1a;随着中国经济的快速发展&#xff0c;…...

skywalking

部署&#xff1a; docker部署方式 docker-compose.yaml version: 3 services:elasticsearch:build:context: elasticsearchrestart: alwaysnetworks:- skywalking_netcontainer_name: elasticsearchimage: elasticsearch:7.17.6environment:- "discovery.typesingle-no…...

江苏开放大学2024年春《大学英语(D) 060108》第二次过程性考核作业参考答案

答案&#xff1a;更多答案&#xff0c;请关注【电大搜题】微信公众号 答案&#xff1a;更多答案&#xff0c;请关注【电大搜题】微信公众号 答案&#xff1a;更多答案&#xff0c;请关注【电大搜题】微信公众号 单选题 1从选项中选出翻译最为准确的一项。 We cannot help …...

dockerfile制作-pytoch+深度学习环境版

你好你好&#xff01; 以下内容仅为当前认识&#xff0c;可能有不足之处&#xff0c;欢迎讨论&#xff01; 文章目录 文档内容docker相关术语docker常用命令容器常用命令根据dockerfile创建容器dokerfile文件内容 docker问题&#xff1a;可能的原因和解决方法示例修改修改后的D…...

YOLOv8结合SCI低光照图像增强算法!让夜晚目标无处遁形!【含端到端推理脚本】

这里的"SCI"代表的并不是论文等级,而是论文采用的方法 — “自校准光照学习” ~ 左侧为SCI模型增强后图片的检测效果,右侧为原始v8n检测效果 这篇文章的主要内容是通过使用SCI模型和YOLOv8进行算法联调,最终实现了如上所示的效果:在增强图像可见度的同时,对图像…...

视频监控/云存储/AI智能分析平台EasyCVR集成时调用接口报跨域错误的原因

EasyCVR视频融合平台基于云边端架构&#xff0c;可支持海量视频汇聚管理&#xff0c;能提供视频监控直播、云端录像、云存储、录像检索与回看、智能告警、平台级联、智能分析等视频服务。平台兼容性强&#xff0c;支持多协议、多类型设备接入&#xff0c;包括&#xff1a;国标G…...

VuePress基于 Vite 和 Vue 构建优秀框架

VitePress 是一个静态站点生成器 (SSG)&#xff0c;专为构建快速、以内容为中心的站点而设计。简而言之&#xff0c;VitePress 获取用 Markdown 编写的内容&#xff0c;对其应用主题&#xff0c;并生成可以轻松部署到任何地方的静态 HTML 页面。 VitePress 附带一个用于技术文档…...

冒泡排序,选择排序,插入排序,希尔排序,基数排序,堆排序代码分析(归并排序和快速排序后续更新)

所有的算法都是这样&#xff0c;算法思想最重要&#xff0c;其次是实现过程&#xff0c;最后才是实现的代码 上战伐谋&#xff0c;我们只要明确了其算法思想和实现过程&#xff0c;所有算法都是纸老虎&#xff0c;所有算法题都是纸老虎 笔者才疏学浅&#xff0c;也算是刚刚接…...

从入门到精通:NTP卫星时钟服务器技术指南

从入门到精通&#xff1a;NTP卫星时钟服务器技术指南 从入门到精通&#xff1a;NTP卫星时钟服务器技术指南 一、 产品功能 卫星时钟服务器是一款采用GPS或北斗卫星提供高精度网络时间服务的产品。卫星天线安装简便&#xff08;根据天线所放位置提示实时卫星颗数&#xff09;&a…...

OpenResty基于来源IP和QPS来限流

Nginx 经典限流法 ngx_http_limit_req_module 和 ngx_http_limit_conn_module&#xff0c;可以在代理层面对服务进行限流和熔断。 http {# 请求限流定义1:# - $binary_remote_addr&#xff1a;限制对象(客户端)# - zone&#xff1a;定义限制(策略)名称# - 10m&#xff1a;用十…...

面对AI技术创业的挑战以及提供给潜在创业者的一些建议

面对AI创业的挑战 AI技术创业虽然机遇众多&#xff0c;但也面临不少挑战&#xff0c;理解这些挑战并寻找应对策略是创业成功的关键。 技术挑战 AI技术的快速发展意味着创业者需要持续学习和更新知识库&#xff0c;以保持技术竞争力。同时&#xff0c;AI项目往往需要处理大量数…...

`require`与`import`的区别

require与import的区别主要体现在以下几个方面&#xff1a; 1.加载时间不同。require是在运行时加载模块&#xff0c;这意味着模块的加载和执行可以在代码的任何地方进行&#xff0c;也可以在运行时根据条件动态地加载不同的模块&#xff1b;import是在编译时加载模块&#xf…...

中介者模式:优雅解耦的利器

在软件设计中&#xff0c;随着系统功能的不断扩展&#xff0c;对象之间的依赖关系往往会变得错综复杂&#xff0c;导致系统难以维护和扩展。为了降低对象之间的耦合度&#xff0c;提高系统的可维护性和可扩展性&#xff0c;设计模式应运而生。中介者模式&#xff08;Mediator P…...

Ubuntu20.04安装MatlabR2018a

一、安装包 安装包下载链接 提取码&#xff1a;kve2 网上相关教程很多&#xff0c;此处仅作为安装软件记录&#xff0c;方便后续软件重装&#xff0c;大家按需取用。 二、安装 1. 相关文件一览 下载并解压文件后&#xff0c;如下图所示&#xff1a; 2. 挂载镜像并安装 2…...

基于SpringBoot的图书馆管理系统设计与实现

介绍 基于&#xff1a;java8 SpringBoot thymeleaf MySQL8.0.17 mybatis-plus maven Xadmin 实现图书馆管理系统 系统要实现如下的基本管理功能&#xff1a; &#xff08;1&#xff09;用户分为两类&#xff1a;管理员&#xff0c;一般用户。 &#xff08;2&#xff09…...

网易云首页单页面html+css

网页设计与网站建设作业htmlcss 预览 源码查看https://hpc.baicaitang.cn/2083.html...

acwing算法提高之图论--最小生成树的典型应用

目录 1 介绍2 训练 1 介绍 本专题用来记录使用prim算法或kruskal算法求解的题目。 2 训练 题目1&#xff1a;1140最短网络 C代码如下&#xff0c; #include <iostream> #include <cstring>using namespace std;const int N 110, INF 0x3f3f3f3f; int g[N][N…...

springcloud基本使用二(远程调用)

创建两个springboot maven子项目 子项目名称分别为order-server和user-server 配置user-server子项目: 所需依赖: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId> </dependenc…...

代码随想录刷题day42| 01背包理论基础分割等和子集

文章目录 day41学习内容一、 01背包之二维数组解法1.1、什么是01背包1.2、动态规划五部曲1.2.1、 确定dp数组&#xff08;dp table&#xff09;以及下标的含义1.2.2、确定递推公式1.2.3、 dp数组如何初始化1.2.4、确定遍历顺序1.2.5、计算并返回最终结果 二、 01背包之一维数组…...

Python文件操作命令

文件操作 我知道你最近很累&#xff0c;是那种看不见的、身体上和精神上的疲惫感&#xff0c;但是请你一定要坚持下去。就算无人问津也好&#xff0c;技不如人也好&#xff0c;千万别让烦躁和焦虑毁了你的热情和定力。别贪心&#xff0c;我们不可能什么都有&#xff0c;也别灰心…...

CSS面试题---基础

1、css选择器及优先级 选择器优先级&#xff1a;内联样式>id选择器>类选择器、属性选择器、伪类选择器>标签选择器、微元素选择器 注意&#xff1a; !important优先级最高&#xff1b; 如果优先级相同&#xff0c;则最后出现的样式生效&#xff1b; 继承得到的样式优先…...

OpenHarmony实战开发-分布式数据管理

​介绍 本示例展示了在eTS中分布式数据管理的使用&#xff0c;包括KVManager对象实例的创建和KVStore数据流转的使用。 通过设备管理接口ohos.distributedDeviceManager &#xff0c;实现设备之间的kvStore对象的数据传输交互&#xff0c;该对象拥有以下能力详见 ;1、注册和解…...

微服务(基础篇-007-RabbitMQ部署指南)

目录 05-RabbitMQ快速入门--介绍和安装_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1LQ4y127n4?p65&vd_source60a35a11f813c6dff0b76089e5e138cc 1.单机部署 1.1.下载镜像 1.2.安装MQ 2.集群部署 2.1.集群分类 2.2.设置网络 视频地址&#xff1a; 05-Rab…...

C语言一维数组及二维数组详解

引言&#xff1a; 小伙伴们&#xff0c;我发现我正文更新的有些慢&#xff0c;但相信我&#xff0c;每一篇文章真的都很用心在写的&#xff0c;哈哈&#xff0c;在本篇博客当中我们将详细讲解一下C语言中的数组知识&#xff0c;方便大家后续的使用&#xff0c;有不会的也可以当…...