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

今天,咱们就一同来探究 “水果成篮” 和 “找到字符串中所有字母异位词” 这两道经典题目,看看滑动窗口算法是如何在其中施展魔法的🧙♂️。
目录
💯水果成篮
📖题目描述
🧠讲解算法原理
💻代码实现(以 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模式:多模式允许在多种工作…...
窦明—环境和教育对人的影响具象化
窦明—“环境和教育有多影响人”的具象化 本篇载体:窦明与环境 本篇主体:环境和教育对人的影响 很多网友调侃说,窦明前后两世性格变了,连面向都看起来变了 可不是嘛,命相和品相生面相,性格也影响着神态和…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

