算法每日双题精讲 —— 滑动窗口(水果成篮,找到字符串中所有字母异位词)
🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟
别再犹豫了!快来订阅我们的算法每日双题精讲专栏,一起踏上算法学习的精彩之旅吧!💪

今天,咱们就一同来探究 “水果成篮” 和 “找到字符串中所有字母异位词” 这两道经典题目,看看滑动窗口算法是如何在其中施展魔法的🧙♂️。
目录
💯水果成篮
📖题目描述
🧠讲解算法原理
💻代码实现(以 C++ 为例)
💯找到字符串中所有字母异位词
📖题目描述
🧠讲解算法原理
💻代码实现(以 C++ 为例)
💯水果成篮
题目链接👉【力扣】
📖题目描述

根据示例分析,该题的本质就是:找出最长子数组的长度,子数组不超过俩种水果类型
🧠讲解算法原理
解法一:
我们用暴力解法写一下,例如f=[1,2,3,2,2]
依次找出所以的情况👇
代码中我们利用哈希表列举情况,用哈希表统计水果出现的类型数
解法二:
先分析
当我们用暴力解法时,遇到如下情况👇,我们让 left++ ,right 回到 left的位置,继续列举情况
当left++时,区间的 kinds 要么不变,要么减少一个
- 当kinds不变时,right没有必要改变
- 当kinds减少时,right可以继续向后移动
因此我们可以用滑动窗口的解法,right不回退嘛
滑动窗口四大步:
- left=0,right=0
- 进窗口——right右移动的时候
- 判断 出窗口——就是left右移动的时候
- 更新结果
举例: f=[1,2,1,2,3,2,3,3]

每次遍历right,让其放入hash表里面,判断有没有超出类型个数
当hash.length>2时出窗口

left右移动的时候,要根据某个水果种类的数量来进行移动,因此我们创建的hash表要有俩个参数,一个记录种类,一个记录个数
例如下面👇,我们要将left移动到3的前面
💻代码实现(以 C++ 为例)
class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};//统计窗口内出现了多少种结果int ret=0;for(int left=0,right=0,kinds=0;right<fruits.size();right++){if(hash[fruits[right]]==0) kinds++;hash[fruits[right]]++;//进窗口while(kinds>2)//判断{//出窗口hash[fruits[left]]--;if(hash[fruits[left]]==0) kinds--;left++;}ret=max(ret,right-left+1);}return ret;}
};
💯找到字符串中所有字母异位词
题目链接👉【力扣】
📖题目描述

🧠讲解算法原理
1.如何判断俩个字符串是否是异位词?
- 可以先排序再比较,但是时间复杂度为nlogn ,比较大
- 通过统计字符串中字符出现的个数也可以判断,借助hash表即可
2.解决问题
例如
暴力解法:
计入p的长度m ,在S里依次比较

优化解法:
当字符串依次遍历时,
,我们发现ba重复出现,所以我们只要将c从hash表移除,让e加入hash表即可,滑动窗口
滑动窗口四大步:
- left=0,right=0
- 进窗口——right右移动的时候
- 判断 出窗口——就是left右移动的时候
- 更新结果



3.优化:更新结果的判断条件
利用变量count来统计窗口中“有效字符”的个数
使用一个数组
targetCount来记录字符串p中每个字母的出现次数,再使用一个数组windowCount来记录当前窗口内每个字母的出现次数。设一个变量valid来表示窗口内有效字母的数量,初始值为0。然后,将
right指针向右移动,每移动一次,就将新字母在windowCount中的计数加1,并检查该字母的计数是否等于在targetCount中的计数,如果相等,则valid加1。当valid等于p中不同字母的数量时,说明当前窗口是一个字母异位词。此时,将
left指针向右移动,同时更新windowCount和valid,直到valid小于p中不同字母的数量。在移动left指针的过程中,如果窗口内的子串长度等于p的长度,就将left指针的索引加入到结果数组中。重复上述步骤,直到
right指针走到字符串s的末尾。最后,返回结果数组。
💻代码实现(以 C++ 为例)
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> result;// 如果s的长度小于p的长度,直接返回空结果if (s.length() < p.length()) return result;// 用于记录字符串p中每个字母的出现次数vector<int> targetCount(26, 0);// 用于记录当前窗口内每个字母的出现次数vector<int> windowCount(26, 0);int valid = 0;// 初始化targetCount数组for (char c : p) {targetCount[c - 'a']++;}int left = 0, right = 0;while (right < s.length()) {int rightIndex = s[right] - 'a';// 将新字母在windowCount中的计数加1windowCount[rightIndex]++;// 如果该字母的计数小于等于在targetCount中的计数,说明该字母在窗口内的数量还未超过p中该字母的数量,有效字母数量加1if (windowCount[rightIndex] <= targetCount[rightIndex]) {valid++;}// 当窗口大小大于p的长度时,移动left指针缩小窗口while (right - left + 1 > p.length()) {int leftIndex = s[left] - 'a';// 将left指针指向的字母在windowCount中的计数减1windowCount[leftIndex]--;// 如果该字母的计数小于在targetCount中的计数,说明该字母在窗口内的数量已经小于p中该字母的数量,有效字母数量减1if (windowCount[leftIndex] < targetCount[leftIndex]) {valid--;}left++;}// 如果有效字母数量等于p中不同字母的数量,说明当前窗口是一个字母异位词,将left指针的索引加入结果数组if (valid == p.length()) {result.push_back(left);}right++;}return result;}
};
我以后还会对 算法 相关知识进行更多的创作,欢迎大家关注我,一起探索 算法 的奇妙世界😜
👉【A Charmer】

相关文章:
算法每日双题精讲 —— 滑动窗口(水果成篮,找到字符串中所有字母异位词)
🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟 别再犹豫了!快来订阅我们的算法每日双题精讲专栏,一起踏上算法学习的精彩之旅吧!💪…...
C++ 设计模式:享元模式(Flyweight Pattern)
链接:C 设计模式 链接:C 设计模式 - 单例模式 享元模式(Flyweight Pattern)是一种结构型设计模式,它通过共享尽可能多的相同对象来减少内存使用和提高性能。享元模式适用于大量细粒度对象的场景,这些对象之…...
Docker+Portainer 离线安装
1. Docker安装 步骤一:官网下载 docker 安装包 步骤二:解压安装包; tar -zxvf docker-24.0.6.tgz 步骤三:将解压之后的docker文件移到 /usr/bin目录下; cp docker/* /usr/bin/ 步骤四:将docker注册成系统服务; vim /etc/sy…...
Linux第100步_Linux之设置LCD作为终端控制台和LCD背光调节
KMS是Kemmel Mode Setting的缩写,内核显示模式设置。它主要负责显示的控制,包括屏幕分辨率、屏幕刷新率和颜色深度等等。 CRTC是指显示控制器,在DRM里有多个显存,通过操作CRTC来控制要显示那个显存。 KMS包含了FB框架。DRM驱动默…...
Chapter09 国际化i18n 和 数据校验:Validation
文章目录 1 Java国际化2 Spring6国际化3 使用Spring6国际化4 数据校验:Validation实验一:通过Validator接口实现实验二:Bean Validation注解实现实验三:基于方法实现校验实验四:实现自定义校验 1 Java国际化 示例&…...
活动预告 | Microsoft 安全在线技术公开课:通过扩展检测和响应抵御威胁
课程介绍 通过 Microsoft Learn 免费参加 Microsoft 安全在线技术公开课,掌握创造新机遇所需的技能,加快对 Microsoft Cloud 技术的了解。参加我们举办的“通过扩展检测和响应抵御威胁”技术公开课活动,了解如何更好地在 Microsoft 365 Defen…...
Unresolved plugin: ‘org.apache.maven.plugins:maven-site-plugin:3.12.1‘
问题 使用idea 社区办加载项目提示下面问题: Unresolved plugin: org.apache.maven.plugins:maven-site-plugin:3.12.1 问题解决 maven插件地址: https://maven.apache.org/plugins/maven-dependency-plugin/plugins.html Maven 中央仓库地址&#…...
5个开源RAG框架对比
还在为RAG应用开发头疼吗?别急,今天给大家推荐五款完全开源免费的RAG框架,覆盖自动优化、多模态处理、本地部署、生产环境支持等多种场景,助你轻松搞定RAG开发!👇 1. AutoRAG:自动优化ÿ…...
活动预告 | Microsoft Power Platform 在线技术公开课:实现业务流程自动化
课程介绍 参加“Microsoft Power Platform 在线技术公开课:实现业务流程自动化”活动,了解如何更高效地开展业务。参加我们举办的本次免费培训活动,了解如何借助 Microsoft AI Builder 和 Power Automate 优化工作流。结合使用这些工具可以帮…...
【分布式文件存储系统Minio】2024.12保姆级教程
文章目录 1.介绍1.分布式文件系统2.基本概念 2.环境搭建1.访问网址2.账号密码都是minioadmin3.创建一个桶4.**Docker安装miniomc突破7天限制**1.拉取镜像2.运行容器3.进行配置1.格式2.具体配置 4.查看桶5.给桶开放权限 3.搭建minio模块1.创建一个oss模块1.在sun-common下创建2.…...
解决ssh和git秘钥认证失败问题
已正确上传公钥到远程服务器,但是本地的连接认证还是使用默认秘钥文件名id_rsa或者默认用户名,导致了认证失败,总结了以下解决办法: 1、ssh秘钥认证 远程登录的时候可能ssh客户端默认使用id_rsa文件名秘钥,但是之前生…...
AI安全的挑战:如何让人工智能变得更加可信
引言 随着人工智能(AI)技术在各个领域的广泛应用,尤其是在医疗、金融、自动驾驶和智能制造等行业,AI正在重塑我们的工作和生活方式。从提高生产效率到实现个性化服务,AI带来了前所未有的便利。然而,在享受这…...
腾讯通RTX升级迁移攻略,兼容Linux内核国产系统及移动端
一、腾讯通RTX继续使用的主要难题 腾讯通RTX停更后,用户不仅无法继续获得更新、技术支持和资源下载,还面临着以下无法解决的使用问题: ● 不兼容国产系统与移动端:腾讯通RTX仅支持Windows和Mac操作系统,无法在基于Li…...
用css实现瀑布流布局
上效果 知识理解 column-count: 4; column-gap: 15px;实现固定四行瀑布流布局 columns: 200px auto;column-gap: 15px;由浏览器根据容器的宽度自动调整,尽可能一行多个200px宽度的列数 <!DOCTYPE html> <html lang"en"><head><me…...
FortiAl为擎重塑网络与安全运营未来
在当今数字化浪潮汹涌的时代,网络安全运营的重要性愈发凸显,而人工智能的迅猛发展则如同一股强劲的东风,为这一领域带来了革命性的变革。Fortinet攻防专家邹国雄在《FortiAI:以生成式人工智能(GenAI)简化Fo…...
优化租赁小程序提升服务效率与用户体验的策略与实践
内容概要 在这个快速发展的商业环境中,租赁小程序成为了提升服务效率和用户体验的重要工具。通过对用户需求的深入挖掘,我们发现他们对于功能的便捷性、响应速度和界面的友好性有着极高的期待。因此,针对这些需求,完善租赁小程序…...
基于Python的医院预约挂号与诊断系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...
Spring Boot教程之四十:使用 Jasypt 加密 Spring Boot 项目中的密码
如何使用 Jasypt 加密 Spring Boot 项目中的密码 在本文中,我们将学习如何加密 Spring Boot 应用程序配置文件(如 application.properties 或 application.yml)中的数据。在这些文件中,我们可以加密用户名、密码等。 您经常会遇到…...
Design Compiler:两种工作模式(线负载模式和拓扑模式)
相关阅读 Design Compilerhttps://blog.csdn.net/weixin_45791458/category_12738116.html?spm1001.2014.3001.5482 Design Compiler可以以线负载模式或拓扑模式启动,必须选择其中一个模式。在拓扑模式下还可使用多模式和UPF模式:多模式允许在多种工作…...
窦明—环境和教育对人的影响具象化
窦明—“环境和教育有多影响人”的具象化 本篇载体:窦明与环境 本篇主体:环境和教育对人的影响 很多网友调侃说,窦明前后两世性格变了,连面向都看起来变了 可不是嘛,命相和品相生面相,性格也影响着神态和…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

