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

算法及数据结构系列 - 滑动窗口

news 来源：原创 2025/8/4 17:49:27

系列文章目录

算法及数据结构系列 - 二分查找
算法及数据结构系列 - BFS算法
算法及数据结构系列 - 动态规划
算法及数据结构系列 - 双指针
算法及数据结构系列 - 回溯算法
算法及数据结构系列 - 树

文章目录

滑动窗口
- 框架思路
- 经典题型
- - 76. 最小覆盖子串
  - 567. 字符串的排列
  - 438. 找到字符串中所有字母异位词
  - 3. 无重复字符的最长子串

滑动窗口

框架思路

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0; while (right < s.size()) {// c 是将移入窗口的字符char c = s[right];// 右移窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/printf("window: [%d, %d)\n", left, right);/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d = s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新...}}
}

经典题型

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
说明：

如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

提示：通过valid记录满足条件的字符数;只关注need中的字符
注意: Integer 类型比较不能用 == ！！！！, 要用 equals()

class Solution {public String minWindow(String s, String t) {int left = 0, right = 0;Map<Character, Integer> win = new HashMap<Character, Integer>();Map<Character, Integer> need = new HashMap<Character, Integer>();for(int i = 0; i< t.length(); i++){need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);}int valid = 0;int start = -1, len = Integer.MAX_VALUE;while(right < s.length()){char c = s.charAt(right);right ++;if(need.containsKey(c)){win.put(c, win.getOrDefault(c, 0) + 1);if(win.get(c).equals( need.get(c))){ // 注意：不能用 ==valid ++;}}while(valid == need.size()){if(right - left < len){start = left;len = right - left;}char d = s.charAt(left);left++;if(need.containsKey(d)){if(win.get(d).equals(need.get(d))){valid --;}win.put(d, win.get(d) - 1);}}}return start == -1? "":s.substring(start, start + len);}
}

567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"  
输出: True  
解释: s2 包含 s1 的排列之一 ("ba").

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

class Solution {public boolean checkInclusion(String s1, String s2) {int left = 0, right = 0;int[] win = new int[256];int[] need = new int[256];int needCharSize = 0;for(int i = 0 ; i< s1.length(); i++){if (need[s1.charAt(i)] == 0){needCharSize++;}need[s1.charAt(i)] ++;}int valid = 0;while(right < s2.length()){char c = s2.charAt(right);right++;if(need[c] > 0){win[c]++;if(need[c] == win[c]){valid++;}}while(valid == needCharSize){if(right - left == s1.length()){return true;}char d = s2.charAt(left);left++;if(need[d] > 0){if(need[d] == win[d]){valid--;}win[d]--;}}}return false;}
}

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

class Solution {List<Integer> res = new ArrayList<Integer>();public List<Integer> findAnagrams(String s, String p) {int left = 0, right = 0;int[] win = new int[256];int[] need = new int[256];int needCharSize = 0;for(int i = 0; i< p.length();i++){char c = p.charAt(i);if(need[c] == 0){needCharSize++;}need[c]++;}int valid = 0;while(right < s.length()){char c = s.charAt(right);right++;if(need[c] > 0){win[c] ++;if(win[c] == need[c]){valid ++;}}while(valid == needCharSize){if(right - left == p.length()){res.add(left);}char d = s.charAt(left);left++;if(need[d] > 0){if(need[d] == win[d]){valid --;}win[d] --;}}}return res;}
}

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

class Solution {public int lengthOfLongestSubstring(String s) {int left = 0, right = 0;int[] win = new int[256];int res = 0;while(right < s.length()){char c = s.charAt(right);right++;win[c]++;while(win[c] > 1){// 收缩以满足条件char d = s.charAt(left);left++;win[d]--;}// 满足条件更新结果res = Math.max(res, right - left);}return res;}
}

算法及数据结构系列 - 滑动窗口

系列文章目录算法及数据结构系列 - 二分查找算法及数据结构系列 - BFS算法算法及数据结构系列 - 动态规划算法及数据结构系列 - 双指针算法及数据结构系列 - 回溯算法算法及数据结构系列 - 树文章目录滑动窗口框架思路经典题型76. 最小覆盖子串567. 字符串的排列438. …...

编程日记 2025/8/4 17:49:27

【江协科技STM32】软件SPI读写W25Q64芯片（学习笔记）

SPI通信协议及S为5Q64简介：【STM32】SPI通信协议&W25Q64Flash存储器芯片（学习笔记）-CSDN博客 STM32与W25Q64模块接线： SPI初始化： 片选SS、始终SCK、MOSI都是主机输出引脚，输出引脚配置为推挽输出&…...

编程日记 2025/7/31 20:35:02

2025.3.23周报题目信息摘要Abstract创新点网络架构实验不足以及展望题目信息题目： Enhancement of Hydrological Time Series Prediction with Real-World Time Series Generative Adversarial Network-Based Synthetic Data and Deep Learning Models期刊&…...

编程日记 2025/8/2 19:14:07

Day20-前端Web案例——部门管理

目录部门管理1. 前后端分离开发2. 准备工作2.1 创建Vue项目2.2 安装依赖2.3 精简项目 3. 页面布局3.1 介绍3.2 整体布局3.3 左侧菜单 4. Vue Router4.1 介绍4.2 入门4.3 案例4.4 首页制作 5. 部门管理5.1部门列表5.1.1. 基本布局5.1.2 加载数据5.1.3 程序优化 5.2 新增部门5.3…...

编程日记 2025/7/31 15:41:47

实验3 以太坊交易周期的需求分析

区块链技术实验报告实验名称实验3 以太坊交易周期的需求分析一、实验目的 1、学习并掌握以太坊交易的内容； 2、学习并掌握以太坊交易周期的四个阶段； 3、学习并掌握结构化需求分析方法； 4、学习并掌握面向对象的需求分析方法&…...

编程日记 2025/8/4 15:42:34

Linux 通过压缩包安装 MySQL 并设置远程连接教程

一、引言在 Linux 系统中，有时候我们需要通过压缩包的方式手动安装 MySQL 数据库，并且为了方便在其他设备上对数据库进行管理和操作，还需要设置允许远程连接。本文将详细介绍在 Linux（以 CentOS 为例）系统中通过压缩包安装 MySQL 8 并设置远程连接的步骤。二、安装前准…...

编程日记 2025/8/3 19:29:08

【商城实战(56)】商城数据生命线：恢复流程与演练全解析

【商城实战】专栏重磅来袭！这是一份专为开发者与电商从业者打造的超详细指南。从项目基础搭建，运用 uniapp、Element Plus、SpringBoot 搭建商城框架，到用户、商品、订单等核心模块开发，再到性能优化、安全加固、多端适配&#xf…...

编程日记 2025/8/3 1:04:28

Java学习笔记-XXH3哈希算法

XXH3是由Yann Collet设计的非加密哈希算法，属于XXHash系列的最新变种，专注于极速性能与低碰撞率，适用于对计算效率要求极高的场景。极速性能在RAM速度限制下运行，小数据（如 1-128 字节）处理可达纳秒级&…...

编程日记 2025/7/30 3:56:51

同旺科技USB to SPI 适配器 ---- 指令循环发送功能

所需设备： 内附链接 1、同旺科技USB to SPI 适配器 1、周期性的指令一次输入，即可以使用 “单次发送” 功能，也可以使用 “循环发送” 功能，大大减轻发送指令的编辑效率； 2、 “单次发送” 功能，“发送数据…...

编程日记 2025/7/31 15:23:09

在Mac M1/M2芯片上完美安装DeepCTR库：避坑指南与实战验证

让推荐算法在Apple Silicon上全速运行概述作为推荐系统领域的最经常用的明星库，DeepCTR集成了CTR预估、多任务学习等前沿模型实现。但在Apple Silicon架构的Mac设备上，安装过程常因ARM架构适配、依赖库版本冲突等问题受阻。本文通过20次环境搭建实测…...

编程日记 2025/8/3 2:21:53

【CXX-Qt】2.5 继承

某些 Qt API 要求你从抽象基类中重写某些方法，例如 QAbstractItemModel。为了支持直接从 Rust 中创建这样的子类，CXX-Qt 提供了多种辅助工具。某些基类可能需要特殊的构造参数。这可以通过使用自定义构造函数来实现。访问基类方法要在 Rust 中访…...

编程日记 2025/8/4 1:36:47

Linux系统之美：环境变量的概念以及基本操作

本节重点理解环境变量的基本概念学会在指令和代码操作上查询更改环境变量环境变量表的基本概念父子进程间环境变量的继承与隔离一、引入 1.1 自定义命令（我们的exe） 我们以往的Linux编程经验告诉我们，我们在对一段代码编译形成可执行文件后…...

编程日记 2025/8/4 1:46:14

【nnUnetv2】推理+评估+测试

在 Windows 系统下设置环境变量之前训练和推理的时候开着AutoDL的服务器，是在 Linux 系统下设置的环境变量。但是现在开始研究具体代码了，就在本地跑（一直开着服务器有点费钱），所以就在Windows 系统下设置环境变量。 ①右键点击 “此电脑”，选择 “属性”。 ②在左侧…...

编程日记 2025/8/3 10:43:12

损失函数理解（一）——极大似然估计

本博客内容来自B站up主【王木头学科学】的视频内容习惯看视频的小伙伴可移至视频链接[待补充]：~~~ 首先通俗地解释一下极大似然估计（Maximum Likelihood Estimation，MLE）的思想：通过结果寻找使该结果发生的最可能的原…...

编程日记 2025/7/31 16:14:48

ios端使用TCplayer直播播放三秒直接卡顿bug

1. 查看配置项没问题 setTcPlayer() {let that this;player new TcPlayer("videoPlayer", {live: this.activatPlayType "livePlay" ? true : false,x5_type: "h5",x5_fullscreen: true,systemFullscreen: true,x5_orientation: 1,x5_player…...

编程日记 2025/8/2 13:41:30

大模型-提示词工程与架构

什么是提示工程提示工程（Prompt Engineering）是一门新兴的技术领域，专注于研究如何设计、构建和优化提示词，以充分发挥大模型的潜力。它涉及到对语言结构、任务需求、模型特性等多方面因素的综合考量。提示工程的目标是通过精心…...

编程日记 2025/7/30 23:35:54

高斯数据库-WDR Snapshot生成性能报告

docker 安装高斯数据库： docker pull opengauss/opengauss:latestdocker run --name opengauss --privilegedtrue -d -e GS_PASSWORDopenGauss123 -p 8090:5432 -v /opengauss:/var/lib/opengauss/data opengauss/opengauss:latest 进入容器设置用户权限&#xff…...

编程日记 2025/7/29 23:47:57

损失函数理解（二）——交叉熵损失

损失函数的目的是为了定量描述不同模型（例如神经网络模型和人脑模型）的差异。交叉熵，顾名思义，与熵有关，先把模型换成熵这么一个数值，然后用这个数值比较不同模型之间的差异。为什么要做这一步转换&…...

编程日记 2025/8/1 9:57:54

CSS学习笔记

【1】CSS样式规则【2】CSS样式表引入方式 1、行内式 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"/><meta name"vi…...

编程日记 2025/8/4 8:22:19

AI比人脑更强，因为被植入思维模型【15】马斯洛需求层次理论

马斯洛需求层次模型思维模型定义马斯洛需求层次模型是由美国心理学家亚伯拉罕马斯洛（Abraham Maslow）于1943年提出的一种心理学理论，用于描述人类动机的层次结构。该模型将人类的需求从低到高分为五个层次，分别是生理需求、安…...

编程日记 2025/8/4 13:01:45

cartographer中地图转换

文章目录地图种类栅格地图坐标系种类ros坐标系像素坐标系物理坐标系(世界坐标系) 地图种类栅格地图地图的初始化在Cartographer中，栅格地图通过概率值来表示每个栅格的状态。每个栅格的初始概率值通常设置为0.5，表示未知状态。这种初始化方式允许…...

编程日记 2025/8/3 5:12:58

关于MTU的使用（TCP/IP网络下载慢可能与此有关）

参考链接：告诉你mtu值怎么设置才能网速最好！ -Win7系统之家出现网络速度被限制，可能与MTU值相关，先查看下本机的MTU winR,然后输入：netsh interface ipv4 show subinterfaces ，查看自己网络中的MTU&…...

编程日记 2025/7/26 13:01:45

【AI解题】Cache直接映射地址划分解析

一、问题背景某32位总线处理器的Cache采用直接映射方式，已知 Cache总容量为16KB，每个Cache块大小为16字节。需要确定内存地址中 Offset（块内偏移）、Index（块索引）、Tag（标签） 三部…...

编程日记 2025/7/30 4:40:47

android音频概念解析

音频硬件接口（我们可以理解为ASOC的声卡） 官方代码里叫audio hardware interface 也称为module，定义在services/audiopolicy/config/audio_policy_configuration.xml： 分别有primary，a2dp，usb&#xff0…...

编程日记 2025/8/3 20:43:07

项目生命周期和项目管理生命周期的差异

在项目管理中，明确区分项目生命周期和项目管理生命周期是理解项目运作的关键。以下从定义、阶段划分到实际应用进行系统性分析：一、项目生命周期（Project Life Cycle）定义项目生命周期是项目从启动到结束的自然演进过程，描述项目交付成果的技术性阶段，通常与…...

编程日记 2025/7/31 10:33:30

UDP 协议

文章目录 UDP 协议简介数据包格式UDP 通信流程抓包分析参考本文为笔者学习以太网对网上资料归纳整理所做的笔记，文末均附有参考链接，如侵权，请联系删除。 UDP 协议 UDP 是一种面向无连接的传输层协议，属于 TCP/IP 协议簇的一种。…...

编程日记 2025/8/3 9:36:11

[已解决]jupyter notebook报错 500 : Internal Server Error及notebook闪退

jupyter notebook出现如上图的报错，可以在黑色窗口中检查是为什么报错。我检查发现是nbconvert导致的问题，卸载重装nbconvert。但是这时候出现，jupyter notebook闪退问题。jupyter的黑色窗口出现一秒钟就没了。在Anaconda Prompt中检查ju…...

编程日记 2025/8/2 22:24:54

APM 仿真遥控指南

地面站开发了一段时间了，由于没有硬件，所以一直在 APM 模拟器中验证。我们已经实现了 MAVLink 消息接收和解析，显示无人机状态，给无人机发送消息，实现一键起飞，飞往指定地点，降落，返…...

编程日记 2025/7/30 14:05:21

使用 ncurses 库创建文本用户界面：基础函数详解

简介 ncurses 是一个功能强大的库，用于在 Unix-like 系统中创建文本用户界面。它提供了丰富的函数来控制屏幕上的文本显示、处理键盘输入、绘制图形元素等。本文将详细介绍 ncurses 库中的一些基础函数，包括 printw、wrefresh、获取用户信息、键盘输入、…...

编程日记 2025/7/24 13:29:01

dify创建第一个Agent

1、首先LLM模型必须支持 Function Calling 由于deepseek-R1本地化部署时还不支持，所以使用 qwq模型。 2、创建空白 Agent 3、为Agent添加工具 4、测试当未添加时间工具时询问时间如下 5、开启时间工具询问如下...

编程日记 2025/7/31 8:12:59

nebula graph传统使用Docker进行项目发版

nebula graph传统使用Docker进行项目发版 1. nebula graph服务2. 搭建ES集群3. 注意事项3.1 图数据库的启动顺序3.2 模糊查询失效 1. nebula graph服务 1.在测试服务器中执行如下命令 docker commit 85b6e2b8xxx xxx_nebula_es:1.0.0.2执行docker images之后能看到新的镜像 x…...

编程日记 2025/7/31 11:58:50

OpenCV vs MediaPipe：哪种方案更适合实时手势识别？

引言手势识别是计算机视觉的重要应用，在人机交互（HCI）、增强现实（AR）、虚拟现实（VR）、智能家居控制、游戏等领域有广泛的应用。实现实时手势识别的技术方案主要有基于传统计算机视觉的方法&am…...

编程日记 2025/8/3 22:41:41

PRODIGY: “不折腾人”的蛋白-蛋白/蛋白-小分子结合能计算工具

PRODIGY（全称为 PROtein binDIng enerGY prediction）是一种蛋白质结合能预测工具，可利用蛋白质-蛋白质复合物的三维结构来预测其结合亲和力。PRODIGY 利用一种高效的基于接触的方法，在估计结合自由能和解离常数的同时，…...

编程日记 2025/7/29 12:49:14

IDEA修改默认作者名称

User: IDEA提示注释缺少author信息，但自动设置后，名称不是我想要的默认名称，应该如何修改IDEA里默认的作者名称？ Kimi: 以下是几种修改IntelliJ IDEA中默认作者名称的方法： ### 方法一：修改File and Code …...

编程日记 2025/8/2 16:59:02

【嵌入式学习2】C语言 - VScode环境搭建

目录 ## 语言分类 ## c语言编译器 ## VScode相关配置 ## 语言分类编译型语言：C，C解释型语言：python，JS ## c语言编译器分类GCC 系列MinGWCygwinMSVC系列一套编程语言编译器将GCC编译器和GNU Binutils移植到Win32平台下的产物…...

编程日记 2025/7/29 18:58:58

【TI MSPM0】Timer学习

一、计数器加法计数器：每进入一个脉冲，就加一减法计算器：每进入一个脉冲，就减一当计数器减到0，触发中断 1.最短计时时间当时钟周期为1khz时，最短计时时间为1ms，最长计时时间为65535ms 当时…...

编程日记 2025/7/31 1:32:06

SQL Server数据库慢SQL调优

SQL Server中慢SQL会显著降低系统性能并引发级联效应。首先，用户直接体验响应时间延长，核心业务操作（如交易处理、报表生成）效率下降，导致客户满意度降低甚至业务中断。其次，资源利用率失衡，CPU…...

编程日记 2025/8/4 4:46:59

大数据平台上的数据建模与分析：从数据到决策的跃迁

大数据平台上的数据建模与分析：从数据到决策的跃迁随着数字化转型的深入，大数据平台成为了企业实现智能决策和创新的核心技术基础。大量结构化、半结构化和非结构化数据的生成和存储，促使企业需要更高效的方式来管理、分析、以及从中提取有价值的信息。在这一过程中，数据…...

编程日记 2025/7/29 1:28:20

C++ --- 多态

1 多态的概念多态(polymorphism)的概念：通俗来说，就是多种形态。多态分为编译时多态(静态多态)和运⾏时多态(动态多态)，这⾥我们重点讲运⾏时多态，编译时多态(静态多态)和运⾏时多态(动态多态)。编译时多态(静态多态)主要就是我…...

编程日记 2025/8/4 5:09:00

细说卫星导航：测距定位原理

测距定位原理 1. 伪距测量技术核心原理：卫星发射信号，用户接收并记录传播时间，乘以光速得到距离（伪距）。技术细节： 信号传播路径分析信号结构： 卫星信号包含三部分： 载波&…...

编程日记 2025/7/31 1:32:06

【AI News | 20250322】每日AI进展

AI Repos 1、DeTikZify 可以把草图或图形转换成TikZ代码的模型，可用来绘制复杂的科学图表，输入草图或文字描述即可转换成TikZ代码。DeTikZify强大的地方在于它能理解图表的语义信息， 能识别图表中的不同组成部分及其含义，比如坐标…...

编程日记 2025/8/4 10:42:28

【js逆向入门】图灵爬虫练习平台第九题

地址：aHR0cHM6Ly9zdHUudHVsaW5ncHl0b24uY24vcHJvYmxlbS1kZXRhaWwvOS8 f12进入了debugger，右击选择一律不在此处暂停， 点击继续执行查看请求信息查看载荷，2个加密参数，m和tt 查看启动器，打上断点进来往…...

编程日记 2025/7/29 14:48:04

重新复活的（手机端）一站式应用管理与下载平台

应用乐园（安卓） 应用乐园作者去年3月表示，由于精力问题，要停止维护奇妙搜索、应用乐园、奇妙影视这些软件了。然而最近，令人意外的是，应用乐园竟然“复活”了！更准确地说，它进行了…...

编程日记 2025/7/31 1:22:40

AI密码学

嗯，用户给了一个需要破译的密码文档：“Uif qjh jt po uif usff.”，提示是用字母往前推移1的凯撒密码。首先，我得确认自己是否正确理解提示。凯撒密码通常是将字母按照一定位移来替换，这里的提示是往前推1位&#xff0c…...

编程日记 2025/7/10 2:24:02

Python设计模式 - 适配器模式

定义适配器模式（Adapter Pattern）是一种结构型设计模式，它用于将一个类的接口转换为客户端所期待的另一个接口。注：在适配器模式定义中所提及的接口是指广义的接口，它可以表示一个方法或者一组方法的集合。结构 …...

编程日记 2025/8/4 9:25:29

S32K324 MCAL SPI波特率配置不对问题排查

文章目录前言MCAL配置检查SPI时钟源问题处理总结前言项目开发过程中，MCAL SPI配置时发现实际配置的波特率和用逻辑分析仪采集的时钟频率对不上，实际的频率只有配置的一半，本文记录该问题的排查过程。 MCAL配置检查 MCAL SPI配置波特率在…...

编程日记 2025/7/29 16:11:37

STM32八股【2】-----ARM架构

1、架构包含哪几部分内容寄存器处理模式流水线MMU指令集中断FPU总线架构 2、以STM32为例进行介绍 2.1 寄存器寄存器名称作用R0-R3通用寄存器用于数据传递、计算及函数参数传递；R0 也用于存储函数返回值。R4-R12通用寄存器用于存储局部变量，减少频繁…...

编程日记 2025/7/31 18:14:13

Java 记忆链表，LinkedList 的升级版

文章目录记忆链表 MemoryLinkedList实战源代码众所周知，ArrayList 和 LinkedList 是 Java 集合中两个基本的数据结构，对应数据结构理论中的数组和链表。但在这两个数据结构，开发者们通常使用 ArrayList，而不使用 LinkedList。JD…...

编程日记 2025/8/4 4:59:06

浔川社团官方联合会维权成功

在2025.3.2日，我社团检测文章侵权中，检测出3篇文章疑似遭侵权，随后，总社团联合会立即联系CSDN版权，经过17天的维权，至今日晚，我社团维权成功！侵权文章全部被设置为转载。在此&…...

编程日记 2025/7/10 9:58:10

asp.net core mvc模块化开发

razor类库新建PluginController using Microsoft.AspNetCore.Mvc;namespace RazorClassLibrary1.Controllers {public class PluginController : Controller{public IActionResult Index(){return View();}} }Views下Plugin下新建Index.cshtml {ViewBag.Title "插件页…...

编程日记 2025/7/31 1:29:29