滑动窗口详解
滑动窗口本质其实也是一种双指针算法,只是因为它维护的区间随着遍历的进行在不停变化,所以形象地称为“滑动窗口”
一、⻓度最⼩的⼦数组

题目要求找到满足条件的长度最小的子数组,我们先来想想暴力的做法,再来想想能不能优化,一般来说,这种找子数组的暴力,就是两层for循环枚举左右两个端点,找到符合条件的所有子数组,然后找出最小值,下面画个图给大家分析一下

代码如下
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans=nums.size()+1;for(int left=0,right=0,s=0;right<nums.size();right++){//进窗口s+=nums[right];//判断是否需要出窗口while(s>=target){//更新答案ans=min(ans,right-left+1);s-=nums[left++];}}return ans==nums.size()+1?0:ans;}
};
通过这道题,我们就能总结出一些规律,滑动窗口的题目分为三个步骤,进窗口,判断是否出窗口以及何时更新答案,当然前提是你得先判断出这题是用滑动窗口解
二、将x减到0的最⼩操作数
这题如果你开始模拟左右两个区间之和==x,而没有想过转化条件,那它就会很难解决,但是其实题目可以等价成找元素和==sum(nums)-x的最长子数组的长度,最后用数组长度减去最长子数组长度就能得到最小操作数,而等价后的题目明显和上一道题几乎一样,这里就不具体分析了
代码如下
class Solution {
public:int minOperations(vector<int>& nums, int x) {int n=nums.size();int target=accumulate(nums.begin(), nums.end(), 0)-x;if(target<0) return -1;//注意判断边界条件int ans=n+1;for(int left=0,right=0,s=0;right<nums.size();right++){//进窗口s+=nums[right];//判断是否出窗口while(s>target) s-=nums[left++];//更新答案if(s==target) ans=min(ans,n-(right-left+1));}return ans==n+1?-1:ans;}
};
好,经过上面的题目,我们就已经对滑动窗口的题目更多的认识和了解,关键在于发现题目可以用滑动窗口解决以及维护区间的某些属性,同时两个指针往同一方向移动(即满足某种单调性)---滑动窗口的特征
三、⽔果成篮

这道题目就是维护区间内水果类型是否大于2,思路如下

进窗口-判断是否出窗口-更新答案 的细节在下面的代码里(请细品)
class Solution {
public:int totalFruit(vector<int>& fruits) {int n=fruits.size(),ans=0;int cnt[n];memset(cnt,0,sizeof(cnt));for(int left=0,right=0,s=0;right<n;right++){//进窗口if(++cnt[fruits[right]]==1)//出现次数为1次,说明水果种类增加s+=1;//判断是否出窗口while(s>2){if(--cnt[fruits[left++]]==0)//出现次数为0次,说明水果种类减少s-=1;}ans=max(ans,right-left+1);}return ans;}
};
四、找到字符串中所有字⺟异位词

这题跟上面几题不太一样,这题的窗口长度是固定的,就是查看字符串s中p.size()的窗口有几个是和组成p的字符一样,记录下标,步骤还是 进窗口-判断是否出窗口-更新答案
代码如下
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int>ans;int hash1[26]={0},hash2[26]={0},k=p.size(),cout=0;for(int i=0;i<p.size();i++)hash1[p[i]-'a']++;for(int left=0,right=0;right<s.size();right++){//进窗口char in=s[right];//如果加完之后该字符的数量任然<=p中该字符的数量,说明增加的是有效字符,cout++if(++hash2[in-'a']<=hash1[in-'a']) cout++;//出窗口if(right-left+1>k){char out=s[left++];//如果该字符的个数本就<=p中该字符的数量,说明减少的是有效字符,cout--if(hash2[out-'a']--<=hash1[out-'a'])cout--;}//更新答案if(k==cout) ans.push_back(left);}return ans;}
};
总结:牢记滑动窗口的三个步骤:进窗口,判断是否出窗口以及何时更新答案,稍难的滑动窗口一般都是和哈希表结合起来,主要是在判断进窗口和出窗口的条件上下文章,当然一切的前提是你能想到用滑动窗口来解决问题,当问题和维护一段连续区间的属性有关时,我们就可以想一想滑动窗口
相关文章:
滑动窗口详解
滑动窗口本质其实也是一种双指针算法,只是因为它维护的区间随着遍历的进行在不停变化,所以形象地称为“滑动窗口” 一、⻓度最⼩的⼦数组 题目要求找到满足条件的长度最小的子数组,我们先来想想暴力的做法,再来想想能不能优化&am…...
JAVA -华为真题-分奖金
需求: 公司老板做了一笔大生意,想要给每位员工分配一些奖金,想通过游戏的方式来决定每个人分多少钱。按照员工的工号顺序,每个人随机抽取一个数字。按照工号的顺序往后排列,遇到第一个数字比自己数字大的,那么…...
第二章:25+ Python 数据操作教程(第十八节如何使用 Matplotlib 库在 python 中执行绘图和数据可视化)持续更新中
本教程概述了如何使用 Matplotlib 库在 python 中执行绘图和数据可视化。这篇文章的目的是让您熟悉该库的基础知识和高级绘图功能。它包含几个示例,将为您提供使用 Python 生成绘图的实践经验。 目录 什么是 Matplotlib? Matplotlib 基础知识<...
XShell7 + Xftp7 + IDEA 打包MapReduce程序到集群运行
参考博客 【MapReduce打包成jar上传到集群运行】http://t.csdn.cn/2gK1d 【Xshell7/Xftp7 解决强制更新问题】http://t.csdn.cn/rxiBG IDEA打包MapReduce程序 这里的打包是打包整个项目,后期等学会怎么打包单个指定的mapreduce程序再来更新博客。 1、编译打包 …...
微软D365 入门文章汇总以及各项认证介绍(持续跟新.....)
介绍 希望入门D365的同学们,需要具备的知识点,涉及C#,WebApi,前端知识,Power Platform等知识,以及Azure的知识点等,需要有了解。 实施Microsoft Dynamics 365 CE (12章)…...
vscode搭建Django自带后台管理系统
文章目录 一、django自带的后台管理系统1. 建表2. 后台管理系统2.1 创建账号2.2 运行后台2.3 登录 二、模版渲染1. 直接将数据渲染到页面2. 数据传递给js 三、数据库1. 查看当前数据库2. 创建UserInfo数据表3. Django rest framework配置 四、vue前端搭建1. 在Django项目的根目…...
Verilog零基础入门(边看边练与测试仿真)-时序逻辑-笔记(4-6讲)
文章目录 第四讲第五讲第六讲 第四讲 1、计数器 代码: //计数器 timescale 1ns/10ps module counter(clk,res,y); input clk; input res; output[7:0] y;reg[7:0] y; wire[7:0] sum;//1运算的结果(1࿰…...
2023-09-12力扣每日一题
链接: 1462. 课程表 IV 题意 一个pair<int,int>表示a是b的前置 进行n次查询,查询q是否是p的前置(可以不是直接前置) 解: 就是要把01、12、13这种能转换出02、03,弗洛伊德即可 无环无负权 实际…...
leetcode面试题:交换和(三种方法实现)
交换和: 给定两个整数数组,请交换一对数值(每个数组中取一个数值),使得两个数组所有元素的和相等。 返回一个数组,第一个元素是第一个数组中要交换的元素,第二个元素是第二个数组中要交换的元…...
前端可视化界面开发技术:实战与优化
引言 在当今的互联网时代,数据可视化已经成为信息展示和交互的重要方式。特别是在前端开发领域,可视化界面的应用越来越广泛,涉及到数据监控、分析和决策等多种场景。本文将深入探讨前端可视化界面开发的关键技术,通过实例解析提…...
Python实现机器学习(下)— 数据预处理、模型训练和模型评估
前言:Hello大家好,我是小哥谈。本门课程将介绍人工智能相关概念,重点讲解机器学习原理机器基本算法(监督学习及非监督学习)。使用python,结合sklearn、Pycharm进行编程,介绍iris(鸢尾…...
树结构处理,list和tree互转
1、实体类 package com.iot.common.test.entity;import lombok.Data;import java.util.List;/*** description:* author:zilong* date:2023/9/8*/ Data public class Node {//idprivate String id;//父节点idprivate String pId;//名称private String name;//编码private Stri…...
可视化大屏设计模板 | 主题皮肤(报表UI设计)
下载使用可视化大屏设计模板,减少重复性操作,提高报表制作效率的同时也确保了报表风格一致,凸显关键数据信息。 软件:奥威BI系统,又称奥威BI数据可视化工具 所属功能板块:主题皮肤上传下载(数…...
Spring Boot + Vue的网上商城之客服系统实现
Spring Boot Vue的网上商城之客服系统实现 在网上商城中,客服系统是非常重要的一部分,它能够为用户提供及时的咨询和解答问题的服务。本文将介绍如何使用Spring Boot和Vue.js构建一个简单的网上商城客服系统。 思路 在本教程中,我们学习了…...
RabbitMQ: return机制
1. Return机制 Confirm只能保证消息到达exchange,无法保证消息可以被exchange分发到指定queue。 而且exchange是不能持久化消息的,queue是可以持久化消息。 采用Return机制来监听消息是否从exchange送到了指定的queue中 2.Java的实现方式 1.导入依赖 &l…...
记录一些奇怪的报错
错误:AttributeError: module distutils has no attribute version 解决方案: 第一步:pip uninstall setuptools 第二步:conda install setuptools58.0.4 错误:ModuleNotFoundError: No module named _distutils_hac…...
Ubuntu 安装redis数据库,并设置开机自启动
1、下载安装包 wget http://download.redis.io/releases/redis-7.0.9.tar.gz 2、解压 tar -zxvf redis-7.0.9.tar.gz 3、复制到解压缩的包移动到/usr/local/ sudo mv ./redis-7.0.9 /usr/local/ 4、编译 cd /usr/local/redis-7.0.9 sudo make 5、测试: 时间会比较长࿰…...
基于开源模型搭建实时人脸识别系统(五):人脸跟踪
继续填坑,之前已经讲了人脸检测,人脸识别实战之基于开源模型搭建实时人脸识别系统(二):人脸检测概览与模型选型_开源人脸识别模型_CodingInCV的博客-CSDN博客,人脸检测是定位出画面中人脸的位置,…...
VUE | 配置环境变量
本篇目录 1. 创建开发环境配置文件2. 创建正式环境配置文件3. 在代码中访问环境变量4. 加载环境变量 在 Vue 项目中是使用 .env 文件来定义和使用不同的环境变量,这些文件在 Vue 项目根目录下创建。推荐有几种环境就创建几个 .env 文件,下面就开发环境和…...
Dynamic-TP入门初探
背景 在使用线程池的过程中,会出现一些痛点: 代码中创建了一个线程池,但是不知道那几个核心参数设置多少比较合适。凭经验设置参数值,上线后发现需要调整,改代码重新发布服务,非常麻烦。线程池相对开发人…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

