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

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

  1. 使用map记录下字符串p中每个字符出现的次数
  2. 使用滑动窗口算法, 遍历字符串s, 窗口大小固定为p的大小
  3. 窗口每次只向右走一步, 每一轮将窗口右端点处的字符在map中对应的次数-1, 将左端点处的字符在map中的次数+1
  4. 如果窗口中所有字符出现的次数与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

  1. 使用fre这个map记录下字符串p中每个字符出现的次数, count记录窗口中满足字谜条件的字符个数
  2. 使用滑动窗口算法, 遍历字符串s, 设置两个指针left和right, 开始指向0
  3. right指针向右移动, 每次移动一步, 如果right指向的字符在p中出现过, count++, 表示窗口中满足条件的字符个数+1
  4. right指向的字符在fre中的次数-1, 表示该字符已经被使用过
  5. 如果right-left+1 == p的长度, 说明找到了一个窗口大小为p的长度的窗口
  6. 如果count == p的长度, 说明窗口中的字符串满足字谜的条件, 将left指向的index加入答案
  7. 如果left指向的字符在p中出现过, count–, 表示窗口中满足条件的字符个数-1
  8. left指向的字符在fre中的次数+1, 恢复初始状态, 表示该字符可以再次使用
  9. 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&#xff1f;MyBatis是一款优秀的持久层框架&#xff0c;支持自定义sql&#xff0c;存储过程以及高级映射。MyBatis就是可以让我们更加简单的实现程序和数据库之间进行交互的一个工具。可以让我们更加简单的操作和读取数据库的内容。MyBatis的官网&#xff1a;htt…...

R语言基础(五):流程控制语句

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

【Java开发】设计模式 02:工厂模式

1 工厂模式介绍工厂模式&#xff08;Factory Pattern&#xff09;是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式&#xff0c;它提供了一种创建对象的最佳方式。在工厂模式中&#xff0c;我们在创建对象时不会对客户端暴露创建逻辑&#xff0c;并且是通过使…...

合并两个链表(自定义位置合并与有序合并)LeetCode--OJ题详解

图片: csdn 自定义位置合并 问题&#xff1a; 给两个链表 list1 和 list2 &#xff0c;它们包含的元素分别为 n 个和 m 个。 请你将 list1 中 下标从 a 到 b 的全部节点都删除&#xff0c;并将list2 接在被删除节点 的位置。 比如&#xff1a; 输入&#xff1a;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的用法

以下内容源于网络资源的学习与整理&#xff0c;如有侵权请告知删除。 一、工具简介 objcopy主要用来转换目标文件的格式。 在实际开发中&#xff0c;我们会用该工具进行格式转换与内容删除。 &#xff08;1&#xff09;在链接完成后&#xff0c;将elf格式的.out文件转化为bi…...

Windows使用Stable Diffusion时遇到的各种问题和知识点整理(更新中...)

Stable Diffusion安装完成后&#xff0c;在使用过程中会出现卡死、文件不存在等问题&#xff0c;在本文中将把遇到的问题陆续记录下来&#xff0c;有兴趣的朋友可以参考。 如果要了解如何安装sd&#xff0c;则参考本文《Windows安装Stable Diffusion WebUI及问题解决记录》。如…...

MySQL workbench基本查询语句

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

软件测试详解

文章目录一、软件危机&#xff08;一&#xff09;概念&#xff08;二&#xff09;产生软件危机的原因&#xff08;三&#xff09;消除软件危机的途径二、软件过程模型&#xff08;一&#xff09;软件生命周期概念&#xff08;二&#xff09;软件开发模型1. 瀑布模型2. 螺旋模型…...

YOLOS学习记录

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

数组边遍历(for循环)边删除为什么删不干净 及三种实现删除的方法

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

环境配置之Keepass

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

Java 电话号码的组合

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

MATLAB——将直接型转化为并联型和级联型

题目1(IIR)&#xff1a; 已知一个系统的传递函数为&#xff1a; H&#xff08;z&#xff09;8−4z−111z−2−2z−31−1.25z−10.75z−2−0.125z−3H&#xff08;z&#xff09;\frac{8-4z^{-1}11z^{-2}-2z^{-3}}{1-1.25z^{-1}0.75z^{-2}-0.125z^{-3}}H&#xff08;z&#xff09…...

.NET Framework .NET Core与 .NET 的区别

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

carla与ros2的自动驾驶算法-planning与control算法开发与仿真

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

corn表达式

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

推荐系统中对抗性机器学习-文献综述与未来发展整理分享

对抗学习是一种机器学习技术&#xff0c;旨在通过提供欺骗性输入来欺骗模型。最常见的原因是导致机器学习模型出现故障。大多数机器学习技术旨在处理特定的问题集&#xff0c;其中从相同的统计分布&#xff08;IID&#xff09;生成训练和测试数据。当这些模型应用于现实世界时&…...

Proteus8.15安装教程

1、解压Proteus8.15 安装包&#xff0c;然后双击进去&#xff0c;找到setup文件&#xff0c;右键&#xff0c;以管理员身份运行。 2、需要安装一些插件&#xff0c;点击“next”。把插件安装完成。 点击“finfish” 点击“install” 点击“Cancel” 3、如果没有上面步骤&…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...