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

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

题目解析
所谓的异位词,就是一个单词中的字母,打乱顺序,重新排列得到的单词
如: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 授…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving
地址:LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂,正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...
