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

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

题目解析
所谓的异位词,就是一个单词中的字母,打乱顺序,重新排列得到的单词
如: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 授…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
