LeetCode 438. Find All Anagrams in a String
LeetCode 438. Find All Anagrams in a String
题目描述
Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
思路 1
- 使用map记录下字符串p中每个字符出现的次数
- 使用滑动窗口算法, 遍历字符串s, 窗口大小固定为p的大小
- 窗口每次只向右走一步, 每一轮将窗口右端点处的字符在map中对应的次数-1, 将左端点处的字符在map中的次数+1
- 如果窗口中所有字符出现的次数与map中数据一致, 就说明匹配到了一个Anagrams
数据结构 1
var (// 记录p中每个字符出现的次数, 因为只有小写字母, 所以map的大小为26fre = make(map[byte]int, 26)// 记录窗口中每个字符出现的次数window = make(map[byte]int, 26)// 记录匹配到的Anagrams的起始位置ans []int
)
算法 1
func findAnagrams(s string, p string) []int {// 如果s的长度小于p的长度, 说明s中不可能存在p的Anagramsif len(s) < len(p) {return []int{}}for i := range p {// 初始化frefre[p[i]]++// 初始化windowwindow[s[i]]++}// 如果初始化后, 窗口中的字符出现的次数与p中的字符出现的次数一致, 说明s的前len(p)个字符就是p的Anagramsif equal(fre, window) {ans = append(ans, 0)}// 遍历s, 每次窗口向右滑动一步for i := len(p); i < len(s); i++ {// 窗口向右滑动, 右端点处的字符在map中对应的次数-1window[s[i-len(p)]]--// 窗口向右滑动, 左端点处的字符在map中对应的次数+1window[s[i]]++// 如果窗口满足字谜的要求if equal(fre, window) {// 把窗口的起始位置加入ansans = append(ans, i-len(p)+1)}}return ans
}// 判断两个map是否相等
func equal(a, b map[byte]int) bool {// 遍历a, a中的字符在b中出现的次数不一致, 说明两个map不相等for i, va := range a {if va != b[i] {return false}}return true
}
思路 2
- 使用fre这个map记录下字符串p中每个字符出现的次数, count记录窗口中满足字谜条件的字符个数
- 使用滑动窗口算法, 遍历字符串s, 设置两个指针left和right, 开始指向0
- right指针向右移动, 每次移动一步, 如果right指向的字符在p中出现过, count++, 表示窗口中满足条件的字符个数+1
- right指向的字符在fre中的次数-1, 表示该字符已经被使用过
- 如果right-left+1 == p的长度, 说明找到了一个窗口大小为p的长度的窗口
- 如果count == p的长度, 说明窗口中的字符串满足字谜的条件, 将left指向的index加入答案
- 如果left指向的字符在p中出现过, count–, 表示窗口中满足条件的字符个数-1
- left指向的字符在fre中的次数+1, 恢复初始状态, 表示该字符可以再次使用
- left指针向右移动一步, left++
数据结构 2
var (// 字符串s的长度slen = len(s)// 字符串p的长度plen = len(p)// 记录p中每个字符出现的次数, 因为只有小写字母, 所以map的大小为26 freq = make(map[byte]int, 26)// 记录匹配到的Anagrams的起始位置ans = make([]int, 0, slen)
)
算法 2
func findAnagrams(s string, p string) []int {if slen < plen {return []int{}}for i := range p {freq[p[i]]++}for left, right, count := 0, 0, 0; right < slen; right++ {c := s[right]// 判断right指向的字符在p中有没有出现if v := freq[c]; v > 0 {count++ // 窗口中满足条件的字符个数+1}freq[c]-- // 出现过则次数-1if right-left+1 == plen { // 如果找到了窗口大小为p长度的窗口if count == plen { // 如果窗口中的字符串满足字谜的条件ans = append(ans, left) // 将left指向的index加入答案}// 如果left指向的字符在p中出现过if v := freq[s[left]]; v >= 0 {// 表示窗口中满足条件的字符个数-1count--}// 窗口左边界前进1步freq[s[left]]++left++}}return ans
}
相关文章:
LeetCode 438. Find All Anagrams in a String
LeetCode 438. Find All Anagrams in a String 题目描述 Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a…...

MyBatis-1:基础概念+环境配置
什么是MyBatis?MyBatis是一款优秀的持久层框架,支持自定义sql,存储过程以及高级映射。MyBatis就是可以让我们更加简单的实现程序和数据库之间进行交互的一个工具。可以让我们更加简单的操作和读取数据库的内容。MyBatis的官网:htt…...

R语言基础(五):流程控制语句
R语言基础(一):注释、变量 R语言基础(二):常用函数 R语言基础(三):运算 R语言基础(四):数据类型 6.流程控制语句 和大多数编程语言一样,R语言支持选择结构和循环结构。 6.1 选择语句 选择语句是当条件满足的时候才执行…...

【Java开发】设计模式 02:工厂模式
1 工厂模式介绍工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。在工厂模式中,我们在创建对象时不会对客户端暴露创建逻辑,并且是通过使…...

合并两个链表(自定义位置合并与有序合并)LeetCode--OJ题详解
图片: csdn 自定义位置合并 问题: 给两个链表 list1 和 list2 ,它们包含的元素分别为 n 个和 m 个。 请你将 list1 中 下标从 a 到 b 的全部节点都删除,并将list2 接在被删除节点 的位置。 比如: 输入:list1 [1…...
Java编程问题总结
Java编程问题总结 整理自 https://github.com/giantray/stackoverflow-java-top-qa 基础语法 将InputStream转换为String apache commons-io String content IOUtils.toString(new FileInputStream(file), StandardCharsets.UTF_8); //String value FileUtils.readFileT…...
binutils工具集——objcopy的用法
以下内容源于网络资源的学习与整理,如有侵权请告知删除。 一、工具简介 objcopy主要用来转换目标文件的格式。 在实际开发中,我们会用该工具进行格式转换与内容删除。 (1)在链接完成后,将elf格式的.out文件转化为bi…...

Windows使用Stable Diffusion时遇到的各种问题和知识点整理(更新中...)
Stable Diffusion安装完成后,在使用过程中会出现卡死、文件不存在等问题,在本文中将把遇到的问题陆续记录下来,有兴趣的朋友可以参考。 如果要了解如何安装sd,则参考本文《Windows安装Stable Diffusion WebUI及问题解决记录》。如…...

MySQL workbench基本查询语句
1.查询所有字段所有记录 SELECT * FROM world.city; select 表示查询;“*” 称为通配符,也称为“标配符”。表示将表中所有的字段都查询出来;from 表示从哪里查询;world.city 表示名为world的数据库中的city表; 上面…...

软件测试详解
文章目录一、软件危机(一)概念(二)产生软件危机的原因(三)消除软件危机的途径二、软件过程模型(一)软件生命周期概念(二)软件开发模型1. 瀑布模型2. 螺旋模型…...

YOLOS学习记录
在前面,博主已经完成了YOLOS项目的部署与调试任务,并在博主自己构造的数据集上进行了实验,实验结果表明效果并不显著,其实这一点并不意外,反而是在情理之中。众所周知,Transformer一直以来作为NLP领域的带头…...

数组边遍历(for循环)边删除为什么删不干净 及三种实现删除的方法
文章目录1、为什么删不干净倒序删迭代器lambda表达式删除为什么说数组边for循环遍历边删除会出现删不干净的情况1、为什么删不干净 先写一个例子:可以先猜一下控制台会打印出什么内容? public class removeIterator {public static void main(String[]…...

环境配置之Keepass
前言很久以前,就有了想要一个自己密码管理器的念头。毕竟,即使浏览器能记住各个网站的账号密码,但是在登录单独客户端的时候,仍然要翻找密码。为了省事,也曾经是一个密码走天下。然后被劫持了QQ给同学发黄色小网站&…...

Java 电话号码的组合
电话号码的字母组合中等给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。示例 1:输入:digits "23…...

MATLAB——将直接型转化为并联型和级联型
题目1(IIR): 已知一个系统的传递函数为: H(z)8−4z−111z−2−2z−31−1.25z−10.75z−2−0.125z−3H(z)\frac{8-4z^{-1}11z^{-2}-2z^{-3}}{1-1.25z^{-1}0.75z^{-2}-0.125z^{-3}}H(z)…...

.NET Framework .NET Core与 .NET 的区别
我们在创建C#程序时,经常会看到目标框架以下的选项,那么究竟有什么区别? 首先 .NET是一种用于构建多种应用的免费开源开发平台,可以使用多种语言,编辑器和库开发Web应用、Web API和微服务、云中的无服务器函数、云原生应用、移动应用、桌面应用、Windows WPF、Windows窗体…...

carla与ros2的自动驾驶算法-planning与control算法开发与仿真
欢迎仪式 carla与ros2的自动驾驶算法-planning与control算法开发与仿真欢迎大家来到自动驾驶Player(L5Player)的自动驾驶算法与仿真空间,在这个空间我们将一起完成这些事情: 控制算法构建基础模块并仿真调试:PID、LQR、Stanley 、MPC、滑膜控…...

corn表达式
简单理解corn表达式:在使用定时调度任务的时候,我们最常用的,就是cron表达式了。通过cron表达式来指定任务在某个时间点或者周期性的执行。cron表达式配置起来简洁方便,无论是Spring的Scheduled还是用Quartz框架,都支持…...

推荐系统中对抗性机器学习-文献综述与未来发展整理分享
对抗学习是一种机器学习技术,旨在通过提供欺骗性输入来欺骗模型。最常见的原因是导致机器学习模型出现故障。大多数机器学习技术旨在处理特定的问题集,其中从相同的统计分布(IID)生成训练和测试数据。当这些模型应用于现实世界时&…...

Proteus8.15安装教程
1、解压Proteus8.15 安装包,然后双击进去,找到setup文件,右键,以管理员身份运行。 2、需要安装一些插件,点击“next”。把插件安装完成。 点击“finfish” 点击“install” 点击“Cancel” 3、如果没有上面步骤&…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
day51 python CBAM注意力
目录 一、CBAM 模块简介 二、CBAM 模块的实现 (一)通道注意力模块 (二)空间注意力模块 (三)CBAM 模块的组合 三、CBAM 模块的特性 四、CBAM 模块在 CNN 中的应用 一、CBAM 模块简介 在之前的探索中…...

短视频时长预估算法调研
weighted LR o d d s T p 1 − p ( 1 − p ) o d d s T p ( T p o d d s ∗ p ) o d d s p o d d s T o d d s odds \frac{Tp}{1-p} \newline (1-p)odds Tp \newline (Tp odds * p) odds \newline p \frac{odds}{T odds} \newline odds1−pTp(1−p)oddsTp(Tpodds…...

【Redis】Redis 的持久化策略
目录 一、RDB 定期备份 1.2 触发方式 1.2.1 手动触发 1.2.2.1 自动触发 RDB 持久化机制的场景 1.2.2.2 检查是否触发 1.2.2.3 线上运维配置 1.3 检索工具 1.4 RDB 备份实现原理 1.5 禁用 RDB 快照 1.6 RDB 优缺点分析 二、AOF 实时备份 2.1 配置文件解析 2.2 开启…...

vue3+el-table 利用插槽自定义数据样式
<el-table-column label"匹配度" prop"baseMatchingLevel"><template #default"scope"><div :style"{ color: scope.row.baseMatchingLevel > 0.8 ? #00B578 : #FA5151 }">{{ scope.row.baseMatchingLevel }}&l…...

【Zephyr 系列 14】使用 MCUboot 实现 BLE OTA 升级机制:构建安全可靠的固件分发系统
🧠关键词:Zephyr、MCUboot、OTA 升级、BLE DFU、双分区、Bootloader、安全固件管理 📌面向读者:希望基于 Zephyr 为 BLE 设备加入安全 OTA 升级功能的开发者 📊预计字数:5200+ 字 🧭 前言:为什么你需要 OTA? 随着设备部署数量增多与产品生命周期延长,远程升级(…...
Redis——主从哨兵配置
目录 基础概念 一、核心原理 二、核心特性 三、技术意义与应用价值 四、典型应用场景 案例部署 一、主从复制配置命令 二、哨兵模式部署命令 关键注意事项 基础概念 一、核心原理 内存存储与高性能 Redis 所有数据存储于内存中&…...