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

Leetcode刷题详解——找到字符串中所有字母异位词

1. 题目链接:438. 找到字符串中所有字母异位词

2. 题目描述:

给定两个字符串 sp,找到 s 中所有 p异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • sp 仅包含小写字母

3. 解法(滑动窗口+哈希表)

3.1 算法思路:

  • 因为字符串p的异位词的长度一定与字符串p的长度相同,所以我们可以在字符串s中构造一个长度为与字符串p的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量
  • 当窗口中每种字母的数量与字符串p中每种字母的数量相同时,则说明当前窗口为字符串p的异位词
  • 因此可以用两个大小为26的数组来模拟哈希表,一个来保存s中的子串每个字符出现的个数,
  • 另一个来保存p每一个字符出现的个数。这样就能判断两个串是否是异位词

3.2 算法流程:

  1. 初始化hash1数组,用来统计字符串p中每个字符出现的次数。
  2. 初始化hash2数组,用来统计滑动窗口内每个字符出现的次数。
  3. 将滑动窗口的左边界left和右边界right都初始化为0
  4. 遍历字符串s,从左到右依次将字符加入窗口。
  5. 判断是否需要移动窗口。如果窗口长度超过了p的长度,就需要移动窗口,判断是否需要从窗口中移出最左边的字符。
  6. 如果需要移出字符,就从窗口中移出最左边的字符,并更新hash2数组和count变量。
  7. 判断窗口内的字符是否是p的异位词。如果是,将左边界的索引加入结果数组ret
  8. 返回结果数组ret

请添加图片描述

3.3 C++算法代码:

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};//统计字符串p中每个字符出现的次数for(auto ch:p)hash1[ch-'a']++;int hash2[26]={0};//统计窗口里面的每个字符出现的个数int m=p.size();for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];if(++hash2[in-'a']<=hash1[in-'a'])count++;//进窗口+维护countif(right-left+1>m)//判断{char out=s[left++];if(hash2[out-'a']--<=hash1[out-'a'])count--;//出窗口+维护 count}//更新结果if(count==m)ret.push_back(left); }return ret;}
};

相关文章:

Leetcode刷题详解——找到字符串中所有字母异位词

1. 题目链接&#xff1a;438. 找到字符串中所有字母异位词 2. 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找到 s 中所有 p 的 异位词 的子串&#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串&#xff08;包括…...

Android 自定义view 圆形进度条

Android 自定义view 圆形进度条 前言一、码前分析二、开码1.画笔2.弧度3.圆弧的位置4.暴露给外部设置进度条的方法三、使用四、完整代码 总结 前言 先来看看效果&#xff0c;大概要实现这么一个圆形的进度条 一、码前分析 要实现这么一个进度条的效果&#xff0c;实际上是要画…...

混凝土基础的智能设计:VisualFoundation 12.0 Crack

实现混凝土基础的智能设计:工程师依靠 VisualFoundation:使用这个专注的工具可以更轻松、更强大地对基础进行建模。通用 FEA 工具&#xff08;如VisualAnalysis&#xff09;可以做很多事情&#xff0c;但对于特定于基础的工程来说&#xff0c;这更快、更智能。 草图边界 快速绘…...

C++中成员函数的重载覆盖与隐藏

1.重载与覆盖 重载&#xff1a;成员函数被重载的特征&#xff1a;在同一个类中&#xff0c;函数名相同&#xff0c;参数不同&#xff0c;vritual关键字可有可无。 覆盖&#xff1a;覆盖是指派生类函数覆盖基类函数&#xff0c;特征是&#xff1a;在有继承关系的类中&#xff0…...

电子器件系列49:CD4050B缓冲器

同相和反向缓冲器 还搞不懂缓冲电路&#xff1f;看这一文&#xff0c;工作原理作用电路设计使用方法 - 知乎 (zhihu.com) 缓冲器_百度百科 (baidu.com) 1、缓冲器的定义 缓冲器是数字元件的其中一种&#xff0c;它对输入值不执行任何运算&#xff0c;其输出值和输入值一样&…...

Leetcode 349 两个数组的交集 (哈希表)

Leetcode 349 两个数组的交集 &#xff08;哈希表&#xff09; 解法1 &#x1f60b;解法2 解法1 &#x1f60b; 自己的笨比方法:【哇这居然是标准解法之一&#xff0c;我不是笨比&#x1f60b;&#x1f60b;&#x1f60b;】 创建了两个hash数组&#xff0c;nums1出现一个就对应…...

基于YOLOv8模型的水下目标检测系统(PyTorch+Pyside6+YOLOv8模型)

摘要&#xff1a;基于YOLOv8模型的水下目标检测系统可用于日常生活中检测与定位鱼、水母、企鹅、海鹦、鲨鱼、海星、黄貂鱼&#xff0c;利用深度学习算法可实现图片、视频、摄像头等方式的目标检测&#xff0c;另外本系统还支持图片、视频等格式的结果可视化与结果导出。本系统…...

vue-cli脚手架创建项目时报错Error: command failed: npm install --loglevel error

项目背景 环境&#xff1a;vue-cli 5.x 在工程文件中&#xff0c;后端模块wms已经创建完成&#xff0c;现在想新建一个名为vue-web的前端模块 执行命令vue create vue-web时&#xff0c; 报错Error: command failed: npm install --loglevel error 问题分析及解决 排查过程…...

c语言练习92:链表的中间结点

链表的中间结点 链表的结点为空时无法访问其next成员否则会报错 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head){if(h…...

CentOS(4)——关于Linux软件下载时:amd64、x86、x86_64、arm64 的说明

目录 一、简介 二、常见的CPU架构 三、Linux查看CPU架构命令 ①arch命令 ②uname -a 命令 ③lscpu 一、简介 在安装GitLab Runner的时候&#xff0c;去清华源下载RPM包时发现同一个软件有许多不同架构的安装包&#xff0c;常见的有amd64、x86、x86_64、arm64这些架构&am…...

简单易学,让你拥有个性化的二维码

在数字化时代&#xff0c;二维码已经成为了我们日常生活的一部分。然而&#xff0c;大多数二维码都是简单而乏味的&#xff0c;缺乏个性和吸引力。这篇文章将向你介绍如何使用乔拓云等免费在线海报制作工具来制作艺术二维码&#xff0c;让你轻松掌握二维码的美化技巧。 1. 选择…...

开源原生android的视频编辑软件

videoEditAndroid 介绍 开源原生android的视频编辑软件 本人android 新手,也是边写边学习中,感觉写的很乱&#xff0c;功能虽已实现,但是会不断优化代码 也欢迎有兴趣的小伙伴加入 码农不易&#xff0c;欢迎 star 项目页面功能完成列表 视频选择(待完善) 静音 视频编辑 导…...

10kb的照片尺寸怎么弄?几个步骤轻松搞定!

为了图片方便在互联网上分享、传输或存储&#xff0c;我们常常会有缩小图片的需求&#xff0c;那么如何进行操作呢&#xff1f;下面分享了三种实用的方法。 方法一&#xff1a;使用嗨格式压缩大师 1、在电脑上打开安装好的“嗨格式压缩大师”&#xff0c;在首界面中点击“图片…...

uniapp-vue3-微信小程序-标签选择器wo-tag

采用uniapp-vue3实现, 是一款支持高度自定义的标签选择器组件&#xff0c;支持H5、微信小程序&#xff08;其他小程序未测试过&#xff0c;可自行尝试&#xff09; 可到插件市场下载尝试&#xff1a; https://ext.dcloud.net.cn/plugin?id14960 使用示例 <template>&…...

数据结构与算法-(9)---双端队列(Deque)

&#x1f308;write in front&#x1f308; &#x1f9f8;大家好&#xff0c;我是Aileen&#x1f9f8;.希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流. &#x1f194;本文由Aileen_0v0&#x1f9f8; 原创 CSDN首发&#x1f412; 如…...

DTI综述(更新中)

Deep Learning for drug repurposing&#xff1a;methods&#xff0c;datasets&#xff0c;and applications 综述读完&#xff0c;觉得少了点东西&#xff0c;自己写个DTI综述 Databases(包括但不限于文章中的) DATABASEDESCRIBEBindingDB有详细的drug信息和对应的target&a…...

封装一个滑块控制灯光组件

效果如下gif 只进行了基础的事件和布局&#xff0c;可优化的地方&#xff1a;luminance-box这个div加上后&#xff0c;由于和slider-run-way都是absolute定位&#xff0c;导致slider-run-way的点击事件无法设置值&#xff0c;只能通过滑块设置。暂时想不到咋处理&#xff0c;有…...

flutter循环

flutter for循环&#xff1a; Wrap(children: <Widget>[for (int i 0; i < (xx.yy.data?.items?.length ?? 0); i)TextButton(onPressed: (){}, child: Text("${xx.yy.data?.items?[i].name.toString()} (${xx.yy.data?.items?[i].connId.toString()})…...

2.3 如何使用FlinkSQL读取写入到JDBC(MySQL)

1、JDBC SQL 连接器 FlinkSQL允许使用 JDBC连接器&#xff0c;向任意类型的关系型数据库读取或者写入数据 添加Maven依赖 <dependency><groupId>org.apache.flink</groupId><artifactId>flink-connector-jdbc</artifactId><version>3.1…...

Flink日志收集到数据库/kafka

引言 我们做项目过程中发现flink日志不同模式启动&#xff0c;存放位置不同&#xff0c;查找任务日志很不方便&#xff0c;具体问题如下&#xff1a; 原始flink的日志配置文件log4j-cli.properties appender.file.append false&#xff0c;取消追加&#xff0c;直接覆盖掉上…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

tomcat入门

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

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...