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

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

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

题目描述:

        给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

思路分析:

依然是滑动窗口法

        根据题目要求,我们需要在字符串 s寻找字符串 p 的异位词。因为字符串 p 的异位词的长度一定与字符串 p的长度相同,所以我们可以在字符串 s中构造一个长度为与字符串 p 的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量;当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时,则说明当前窗口为字符串 p 的异位词。

优化思路

        在上述方法的基础上,我们不再分别统计滑动窗口和字符串中每种字母的数量,而是统计滑动窗口和字符串 p中每种字母数量的差;并引入变量cnt来记录当前窗口与字符串 p中数量不同的字母的个数,并在滑动窗口的过程中维护它。

        在判断滑动窗口中每种字母的数量与字符串 p中每种字母的数量是否相同时,只需要判断cnt是否为零即可。

代码实现注解:

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer>res=new ArrayList<>();//定义一个一维数组记录字母在两个字符串中出现的差值//cnt[x] = 0  表示 s与p中字母x出现次数相同 都出现了n次//cnt[x] = n  表示 在s中字母x出现次数比p多 多出现了n次//cnt[x] = -n 表示 在s中字母x出现次数比p少 少出现了n次int[]cnt=new int[26];//统计字符数量int n=p.length();int m=s.length();//如果目标字符长度大于原始字符长度,返回空数组if(n>m){return res;}//开始遍历数组,创造窗口滑块,p数组出现的字母数值加一,S数组出现的字母数字减一。//所以当cnt数组上的数值为0是代表在滑块中p和s出现该字母的频率一致for(int i=0;i<n-1;i++){cnt[p.charAt(i)-'a']++;cnt[s.charAt(i)-'a']--;}//将P字符串中的最后一个字母读入cnt中cnt[p.charAt(n-1)-'a']++;int l=0;//将S字符串中的n-1位置上的字母作为滑块的右边界//开始滑动窗口for(int r=n-1;r<m;r++){cnt[s.charAt(r)-'a']--;int o=0;//随着右边界的右移,判断新的右边界。如果cnt数组上的数值为0,那么o赋值为1for(int j=0;j<26;j++){o+=cnt[j]==0?1:0;}//说明s和p的同一个字母出现频率相等if(o==26){res.add(l);}//左边界向右移,缩小窗口cnt[s.charAt(l++)-'a']++;}return res;}
}

相关文章:

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

找到字符串中所有字母异位词 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找到 s 中所有 p 的 异位词 的子串&#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串&#xff08;包括相同的字符串&#xff09;。 示…...

力扣96. 不同的二叉搜索树

Problem: 96. 不同的二叉搜索树 文章目录 题目描述思路复杂度Code 题目描述 思路 一个数字做根节点的话可能的结果为&#xff1a;其左边数字做子树的组合数字乘以其右边数字做子树的个数之积 1.创建备忘录memo&#xff1b; 2.递归分别求取当前数字左边和右边数字做子树的数量&…...

哈希表的用途

...

k8s笔记 | 高度调度

CronJob计划任务 简介&#xff1a;在k8s中周期性运行计划任务&#xff0c;与linux中的crontab相同&#xff1b;注意点 CornJob执行的时间是controller-manager的时间&#xff0c;所以一定要确保controller-manager的时间是准确的&#xff0c;另外cornjob cron表达式 文章参…...

Rom应用开发遇到得一些小bug

记录一些细碎得bug ROM时间类问题 问题描述&#xff1a; 设备拔电重启&#xff0c;ROM时间为默认时间如1970年1月1日&#xff0c;与某些业务场景互斥 问题原因&#xff1a; 后台接口校验https证书校验失败&#xff0c;要求是2年内得请求头校验了时间戳&#xff0c;时间戳过期…...

Python简介

Python简介 1. Python定义 Python 是一种简单易学并且结合了解释性、编译性、互动性和面向对象的脚本语言。Python提供了高级数据结构&#xff0c;它的语法和动态类型以及解释性使它成为广大开发者的首选编程语言。 Python 是解释型语言&#xff1a; 开发过程中没有了编译这个环…...

C++完成特色旅游管理信息系统

背景&#xff1a; 继C完成淄博烧烤节管理系统后&#xff0c;我们来到了特色旅游管理信息系统的代码编写&#xff0c;历史链接点下方。 C完成淄博烧烤节管理系统_淄博烧烤总账管理系统的-CSDN博客 问题描述&#xff1a; 为了更好的管理各个服务小组&#xff0c;开发相应的管…...

贵州大学24计算机考研数据速览,国家重点实验室22408复试线285分!贵州大学计算机考研考情分析!

贵州大学计算机科学与技术学院坐落在贵州大学北校区&#xff08;贵阳花溪&#xff09;。 学院现有教职工139人&#xff0c;其中专职教师126人&#xff0c;教授17人&#xff0c;副教授37人&#xff0c;讲师46人&#xff0c;高级实验师4人&#xff0c;实验师17人。具有博士学位的…...

分区4K对齐那些事,你想知道的都在这里

在对磁盘进行分区时,有一个很重要的注意事项,就是要将分区对齐,不对齐可能会造成磁盘性能的下降。尤其是固态硬盘SSD,基本上都要求4K对齐。磁盘读写速度慢还找不到原因?可能就是4K对齐的锅。那么分区对齐究竟是怎么回事?为什么要对齐?如何才能对齐?如何检测是否对齐呢?…...

达梦数据库学习笔记

架构、特点和基本概念 达梦数据库&#xff08;DM Database&#xff09;是中国达梦数据库有限公司自主研发的关系型数据库管理系统。它广泛应用于政府、金融、电信、能源等行业&#xff0c;具备高性能、高可靠性和高安全性的特点。 架构 达梦数据库的架构设计注重高性能和高可…...

安卓绕过限制直接使用Android/data无需授权,支持安卓14(部分)

大家都知道&#xff0c;安卓每次更新都会给权限划分的更细、收的更紧。   早在安卓11的时候还可以直接通过授权Android/data来实现操作其他软件的目录&#xff0c;没有之前安卓11授权的图了&#xff0c;反正都长一个样&#xff0c;就直接贴新图了。   后面到了安卓12~13的…...

【知识蒸馏】多任务模型 logit-based 知识蒸馏实战

一、什么是逻辑&#xff08;logit&#xff09;知识蒸馏 Feature-based蒸馏原理是知识蒸馏中的一种重要方法&#xff0c;其关键在于利用教师模型的隐藏层特征来指导学生模型的学习过程。这种蒸馏方式旨在使学生模型能够学习到教师模型在特征提取和表示方面的能力&#xff0c;从…...

C:技术面试总结

1 变量的声明和定义: 定义:为变量分配地址和存储空间 声明:不分配地址。一个变量可以在多个地方声明,但只能在一个地方定义。extern修饰的变量声明,说明此变量将在文件以外或文件后面部分定义。 2 局部变量是否能与全局变量重名: 可以,局部变量会屏蔽全局变量 局部…...

OpenHarmony 实战开发——一文总结ACE代码框架

一、前言 ACE_Engine框架是OpenAtom OpenHarmony&#xff08;简称“OpenHarmony”&#xff09;的UI开发框架&#xff0c;为开发者提供在进行应用UI开发时所必需的各种组件&#xff0c;以及定义这些组件的属性、样式、事件及方法&#xff0c;通过这些组件可以方便进行OpenHarmo…...

【数据结构与算法】之堆的应用——堆排序及Top_K问题!

目录 1、堆排序 2、Top_K问题 3、完结散花 个人主页&#xff1a;秋风起&#xff0c;再归来~ 数据结构与算法 个人格言&#xff1a;悟已往之不谏&#xff0c;知来者犹可追 克心守己&#xff0c;律己则安&#xff01; 1、堆排序 对一个无序的数组…...

啊哈!算法-第2章-栈、队列、链表

啊哈!算法-第2章-栈、队列、链表 第1节 解密qq号——队列第2节 解密回文——栈第3节 纸牌游戏——小猫钓鱼第4节 链表第5节 模拟链表 第1节 解密qq号——队列 新学期开始了&#xff0c;小哈是小哼的新同桌(小哈是个大帅哥哦~)&#xff0c;小哼向小哈询问 QQ 号&#xff0c; 小…...

简述 v-if 和 v-show 的区别

v-if 和 v-show 都是 Vue.js 中用于控制元素显示与隐藏的指令&#xff0c;但它们的工作方式有显著的差异。以下是它们之间的主要区别&#xff1a; 渲染方式&#xff1a; v-if&#xff1a;v-if 是“真正”的条件渲染&#xff0c;因为它会确保在切换过程中条件块内的事件监听器和…...

Linux驱动学习之模块化,参数传递,符号导出

1.模块化 1.1.模块化的基本概念&#xff1a; 模块化是指将特定的功能或组件独立出来&#xff0c;以便于开发、测试和维护。在Linux设备驱动中&#xff0c;模块化允许将驱动程序作为内核模块动态加载到系统中&#xff0c;从而提高了系统的灵活性和可扩展性。 1.2.Linux内核模…...

RabbitMQ02-RebbitMQ简介及交换器

一. AMQP协议 什么是AMQP协议 AMQP(Advanced Message Queuing Protocol,高级消息队列协议):它是进程之间传递异步消息的网络协议 AMQP工作过程 发布者通过发布消息&#xff0c;通过交换机&#xff0c;交换机根据路由规则将收到的消息分发交换机绑定的下消息队列&#xff0c;最…...

Matlab自学笔记三十:元胞数组的修改、添加、删除和连接

1.说明 元胞数组的子数组或元素也是元胞型的&#xff0c;其元素内容&#xff08;值&#xff09;是本身类型&#xff0c;因此&#xff0c;在添、删、改和连接处理时&#xff0c;必须明确每个元素的值的类型和大小&#xff0c;否则&#xff0c;编程报错是不可避免的了。看本文前…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...