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

题目要求找到满足条件的长度最小的子数组,我们先来想想暴力的做法,再来想想能不能优化,一般来说,这种找子数组的暴力,就是两层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入门初探
背景 在使用线程池的过程中,会出现一些痛点: 代码中创建了一个线程池,但是不知道那几个核心参数设置多少比较合适。凭经验设置参数值,上线后发现需要调整,改代码重新发布服务,非常麻烦。线程池相对开发人…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...
第八部分:阶段项目 6:构建 React 前端应用
现在,是时候将你学到的 React 基础知识付诸实践,构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段,你可以先使用模拟数据,或者如果你的后端 API(阶段项目 5)已经搭建好,可以直接连…...
FOPLP vs CoWoS
以下是 FOPLP(Fan-out panel-level packaging 扇出型面板级封装)与 CoWoS(Chip on Wafer on Substrate)两种先进封装技术的详细对比分析,涵盖技术原理、性能、成本、应用场景及市场趋势等维度: 一、技术原…...

