算法刷题:找到字符串中所有的字母异位词
找到字符串中所有的字母异位词
- .
- 题目链接
- 题目详情
- 题目解析
- 算法原理
- 滑动窗口流程图
- 定义指针及变量
- 进窗口
- 判断
- 出窗口
- 更新结果
- 我的答案
.

题目链接
找到字符串中所有的字母异位词
题目详情

题目解析
所谓的异位词,就是一个单词中的字母,打乱顺序,重新排列得到的单词
如:abc->bca
那么题目的目的就很明显了,就是要求在s字符串中找到p的异位词(相同组成,不同排列)
我们来模拟找一下
首先,定义两个指针,维护满足异位词的左右边界

使right往右移动

如图,在left与right之间,长度刚好符合p的异位词,此时,就需要对这个字符串进行校验,很,很明显,cba就属于p的异位词,校验成功,将当前异位词的首元素下标记录一下,然后使right继续往右移,但是此时子串的长度就不满足p的异位词了,因此,需要将left也往右移动一位

移动完成之后,此时子串的长度又满足条件了,进行校验,并不是p的异位词,继续移动,直到遍历完整个数组
很明显,整个过程通过两个指针,同向进行遍历来解决问题,而left与right之间,往右移动的过程,与窗口类似,因此我们考虑使用滑动窗口来实现这个过程
算法原理
滑动窗口流程图

定义指针及变量
定义两个指针:left和right,初始值都为0
创建hash表1,用数组模拟,记录p的每个字母出现的个数
创建hash表2,用数组模拟,用来记录子串(窗口)中各个字母出现的个数
定义变量count,来记录窗口中的有效字母的个数
创建链表来存储满足条件的异位词的下标
进窗口
将right所在的字母添加到hash2中,t添加完成之后
如果hash2[s[right]-‘a’]<=hash1[s[right]-‘a’]
说明当前字母是有效字母,就将count加一
判断
判断子串长度是否大于p的异位词的长度
出窗口
当窗口内子串长度大于p的异位词的长度的时候,需要将left所在的字母从hash2中减去1,在减去之前,需要再进行一层判断,判断hash2[s[left]-‘a’]<=hash1[s[left]-‘a’],如果满足,说明减去的是有效字母,因此需要将count进行减一
更新结果
如果有效字母个数count等于p的字母个数,就说明满足p的异位词,将当前子串的下标存进链表中
我的答案
class Solution {public List<Integer> findAnagrams(String ss, String pp) {//定义返回值List<Integer> list = new ArrayList<>();//将ss和pp转换为数组,方便遍历char[]s = ss.toCharArray();char[]p = pp.toCharArray();//创建hash1,统计pint[]hash1 = new int[26];for(char tmp:p){hash1[tmp-'a']++;}//创建hash2,用于统计sint[]hash2 = new int[26];//定义变量int count = 0;//记录有效字母个数for(int left = 0,right = 0;right<s.length;right++){//进窗口hash2[s[right]-'a']++;//维护有效字母个数if(hash2[s[right]-'a']<=hash1[s[right]-'a']) count++;//判断if(right-left+1>p.length){//出窗口//维护有效字母个数if(hash2[s[left]-'a']<=hash1[s[left]-'a']) count--;hash2[s[left]-'a']--;left++;}//更新结果if(count==p.length){list.add(left);}}return list;}
}
相关文章:
算法刷题:找到字符串中所有的字母异位词
找到字符串中所有的字母异位词 .题目链接题目详情题目解析算法原理滑动窗口流程图定义指针及变量进窗口判断出窗口更新结果 我的答案 . 题目链接 找到字符串中所有的字母异位词 题目详情 题目解析 所谓的异位词,就是一个单词中的字母,打乱顺序,重新排列得到的单词 如:abc-&g…...
【Java EE初阶十九】网络原理(四)
4. 数据链路层 数据链路层也有很多种协议,其中一个比较常见常用的,就是“以太网协议”(通过网线/光纤, 来通信所使用的协议叫做以太网协议,以太网是横跨数据链路层 物理层); 4.1 以太网数据帧格式 帧头 载荷(IP 数据…...
12.23 校招 实习 内推 面经
绿*泡*泡VX: neituijunsir 交流*裙 ,内推/实习/校招汇总表格 1、社招&校招 | 轻舟智航 社招 & 2024校招 社招&校招 | 轻舟智航 社招 & 2024校招 2、校招 | 成都精灵云科技2024校园招聘补录 校招 | 成都精灵云科技2024校园招聘补录 …...
FPGA转行ISP的探索之一:行业概览
ISP的行业位置 最近看到一个分析,说FPGA的从业者将来转向ISP(Image Signal Process图像信号处理)是个不错的选择,可以适应智能汽车、AI等领域。故而我查了一下ISP,对它大致有个概念。 传统的ISP对应的是相机公司&…...
Linux系统之部署网页小游戏合集网站
Linux系统之部署网页游戏合集网站 一、项目介绍1.1 项目介绍1.2 自定义配置方法二、本次实践介绍2.1 环境规划2.2 本次实践介绍三、检查本地环境3.1 检查操作系统版本3.2 检查当前yum仓库四、安装httpd软件4.1 检查yum仓库4.2 安装httpd软件4.3 启动httpd服务4.4 查看httpd服务…...
【白嫖8k买的机构vip教程】python(2):python_re模块
python之re模块 一、正则表达式 re模块是python独有的匹配字符串的模块,该模块中提供的很多功能是基于正则表达式实现的,而正则表达式是对字符串进行模糊匹配,提取自己需要的字符串部分,他对所有的语言都通用。注意…...
【CSS】display:flex和display: inline-flex区别
flex:将对象作为弹性伸缩盒显示 inline-flex:将对象作为内联块级弹性伸缩盒显示 DOM结构 <div class"main"><div></div><div></div><div></div><div></div></div>flex .main{…...
rpm安装gitlab
1.1 下载gitlab安装包 使用rpm包安装命令安装gitlab的rpm包,下载地址为https://packages.gitlab.com/gitlab/gitlab-ce社区版本; 推荐使用清华大学镜像:https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el7/gitlab安装包详见࿱…...
图论之dfs与bfs的练习
dfs--深度优选搜索 bfs--广度优先搜索 迷宫问题--dfs 问题: 给定一个n*m的二维迷宫数组其中S是起点,T是终点,*是墙壁(无法通过), .是道路 问从起点S出发沿着上下左右四个方向走,能否走到T点&a…...
Vue练习5:图片的引入
后续会补充 1.require引入 src -> asstes <template><img :src"url"> </template><script> export default {name: App,data(){return{url: require("./assets/logo.png"),}} } </script> 2.import引入 src…...
SpringBoot+Kafka
文章目录 一、依赖二、配置文件三、API1、生产者2、消费者 一、依赖 <!-- spring-kafka(与kafka的版本一致) --> <dependency><groupId>org.springframework.kafka</groupId><artifactId>spring-kafka</artifactId>…...
世界顶级名校计算机专业,都在用哪些书当教材?(文末送书)
目录 01《深入理解计算机系统》02《算法导论》03《计算机程序的构造和解释》04《数据库系统概念》05《计算机组成与设计:硬件/软件接口》06《离散数学及其应用》07《组合数学》08《斯坦福算法博弈论二十讲》参与规则 清华、北大、MIT、CMU、斯坦福的学霸们在新学期里…...
蓝桥杯刷题--python-8(2023 填空题)
0幸运数 - 蓝桥云课 (lanqiao.cn) res=0 for i in range (1,100000000):l_n=[]for j in str(i):l_n.append(int(j))if len(l_n) % 2 ==0:cur =len(l_n)>>1if sum(l_n[:cur])==sum(l_n[cur:]):res+=1 print(res) 0有奖问答 - 蓝桥云课 (lanqiao.cn) dfs def bfs(score, q…...
Eclipse - Reset Perspective
Eclipse - Reset Perspective 1. Window -> Perspective -> Reset Perspective2. Reset Perspective -> YesReferences 1. Window -> Perspective -> Reset Perspective 2. Reset Perspective -> Yes References [1] Yongqiang Cheng, https://yo…...
1.5v的电池电压低于多少v等于没电
对于1.5V的电池,电压低于一定值时就不再适合使用了。具体的电压值取决于电池的类型和使用设备的需求。一般来说, 对于接收设备(如收音机、BB机、遥控机等),每节电池电压一般到1.2V以下就认为没电了。有些电动玩具、剃…...
LabVIEW智能监测系统
LabVIEW智能监测系统 设计与实现一个基于LabVIEW的智能监测系统,通过高效的数据采集和处理能力,提高监测精度和响应速度。系统通过集成传感器技术与虚拟仪器软件,实现对环境参数的实时监测与分析,进而优化监控过程,提…...
代码随想录刷题第34天
第一题是柠檬水找零https://leetcode.cn/problems/lemonade-change/,感觉并没有特别靠近贪心算法,可供讨论的情况非常少,5元收下,10元返5元,20元返15元,对各种找零情况讨论一下即可。 class Solution { pu…...
AMD FPGA设计优化宝典笔记(5)低频全局复位与高扇出
亚军老师的这本书《AMD FPGA设计优化宝典》,他主要讲了两个东西: 第一个东西是代码的良好风格; 第二个是设计收敛等的本质。 这个书的结构是一个总论,加上另外的9个优化,包含的有:时钟网络、组合逻辑、触发…...
14. Qt 程序菜单实现,基于QMainWindow
目录 前言: 技能: 内容: 一、ui中直接添加控件实现 二、 完全通过代码实现菜单 参考: 前言: 基于QMainWindow,两种方式实现菜单:通过直接添加ui控件快速添加菜单和完全通过代码实现菜单&a…...
如何利用SpringSecurity进行认证与授权
目录 一、SpringSecurity简介 1.1 入门Demo 二、认证 编辑 2.1 SpringSecurity完整流程 2.2 认证流程详解 2.3 自定义认证实现 2.3.1 数据库校验用户 2.3.2 密码加密存储 2.3.3 登录接口实现 2.3.4 认证过滤器 2.3.5 退出登录 三、授权 3.1 权限系统作用 3.2 授…...
用while循环语句求和
在“用for循环语句求和”中,学习了for循环语句,这篇博文继续学习另一种形式的循环程序结构while循环语句。while循环语句一般用于事先不能确定循环次数的情况,格式为while 表达式循环体end如果表达式为真,就执行循环体的内容&…...
ET框架:C#全栈游戏开发的热更与服务端重构实践
1. ET框架不是“又一个Unity网络库”,而是重构服务器开发范式的底层工具链很多人第一次看到“ET框架”四个字,下意识会把它归类为“Unity里用的Socket封装库”或者“带点RPC味道的通信中间件”——这种理解偏差,恰恰是踩坑的起点。我2018年在…...
基于伴随方法与Firedrake的PDE-ML可微分集成框架
1. 项目概述:当有限元遇上机器学习在计算科学与工程领域,我们常常面临一个核心挑战:如何高效地求解复杂的物理系统,并在此基础上进行优化、反演或设计。偏微分方程(PDE)是描述这些物理系统(如流…...
Keil MDK许可证错误解决方案与调试技巧
1. 问题现象与背景解析 当使用Keil MDK进行嵌入式开发时,部分用户在编译或调试阶段会遇到"LICENSE: License Mapping Failed"的错误提示。这个报错通常出现在以下两种场景: 编译阶段:在Build Output窗口突然弹出红色错误提示&…...
别再手动写日报了!Claude项目中枢搭建全教程(含API对接、敏感信息脱敏、审计留痕三重安全机制)
更多请点击: https://kaifayun.com 第一章:Claude项目中枢的定位与核心价值 Claude项目中枢是整个AI协作体系的调度核心与语义枢纽,它不直接执行模型推理,而是承担上下文治理、权限编排、多模态协议适配与可信链路审计等关键职能…...
Win11已加密?统信UOS 1060双系统安装后数据盘共享踩坑实录与解决方案
Win11与统信UOS 1060双系统数据共享难题:从加密隔离到无缝互通当Windows 11的BitLocker加密遇上统信UOS的文件系统支持,双系统用户常常陷入一个尴尬境地——明明两块硬盘物理相连,数据却像隔着一道无形的墙。这不是简单的权限问题,…...
边缘计算赋能触觉互联网与数字孪生:架构、挑战与物理治疗实践
1. 从概念到现实:边缘计算如何重塑触觉互联网与人类数字孪生在远程医疗、工业操控乃至未来的元宇宙体验中,我们一直梦想着能突破屏幕的界限,实现“隔空取物”般的真实交互。医生希望远程为病人进行精准的物理治疗,工程师渴望在千里…...
【AI入门知识点】告别繁琐配置!Claude Code + DeepSeek 直连方案打造最强 VSCode 编程助手
在 AI 编程领域,Claude Code 凭借其强大的 Agent 能力(自动读写文件、执行命令)一直是开发者的梦中情“器”。然而,官方 API 的高昂费用和网络限制,让许多国内开发者望而却步。 这篇文章我们不通过 cc-switch 转发请求…...
5分钟永久激活Windows和Office的终极解决方案:KMS智能激活工具完整指南
5分钟永久激活Windows和Office的终极解决方案:KMS智能激活工具完整指南 【免费下载链接】KMS_VL_ALL_AIO Smart Activation Script 项目地址: https://gitcode.com/gh_mirrors/km/KMS_VL_ALL_AIO 还在为Windows系统频繁弹出激活提示而烦恼吗?Offi…...
【限时解密】Lindy自动化方案未公开的4层权限熔断机制:为什么92%的企业跳过这步就触发合规雷区?
更多请点击: https://kaifayun.com 第一章:Lindy人力资源自动化方案的合规性底层逻辑 Lindy人力资源自动化方案并非简单地将流程数字化,而是以全球主流劳动法规为约束边界,将合规性内化为系统架构的刚性层。其底层逻辑建立在“规…...
