Leetcode刷题详解——找到字符串中所有字母异位词
1. 题目链接:438. 找到字符串中所有字母异位词
2. 题目描述:
给定两个字符串
s和p,找到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 * 104s和p仅包含小写字母
3. 解法(滑动窗口+哈希表)
3.1 算法思路:
- 因为字符串p的异位词的长度一定与字符串p的长度相同,所以我们可以在字符串
s中构造一个长度为与字符串p的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量 - 当窗口中每种字母的数量与字符串p中每种字母的数量相同时,则说明当前窗口为字符串
p的异位词 - 因此可以用两个大小为
26的数组来模拟哈希表,一个来保存s中的子串每个字符出现的个数, - 另一个来保存
p每一个字符出现的个数。这样就能判断两个串是否是异位词
3.2 算法流程:
- 初始化
hash1数组,用来统计字符串p中每个字符出现的次数。 - 初始化
hash2数组,用来统计滑动窗口内每个字符出现的次数。 - 将滑动窗口的左边界
left和右边界right都初始化为0。 - 遍历字符串
s,从左到右依次将字符加入窗口。 - 判断是否需要移动窗口。如果窗口长度超过了
p的长度,就需要移动窗口,判断是否需要从窗口中移出最左边的字符。 - 如果需要移出字符,就从窗口中移出最左边的字符,并更新
hash2数组和count变量。 - 判断窗口内的字符是否是
p的异位词。如果是,将左边界的索引加入结果数组ret。 - 返回结果数组
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. 题目链接:438. 找到字符串中所有字母异位词 2. 题目描述: 给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串(包括…...
Android 自定义view 圆形进度条
Android 自定义view 圆形进度条 前言一、码前分析二、开码1.画笔2.弧度3.圆弧的位置4.暴露给外部设置进度条的方法三、使用四、完整代码 总结 前言 先来看看效果,大概要实现这么一个圆形的进度条 一、码前分析 要实现这么一个进度条的效果,实际上是要画…...
混凝土基础的智能设计:VisualFoundation 12.0 Crack
实现混凝土基础的智能设计:工程师依靠 VisualFoundation:使用这个专注的工具可以更轻松、更强大地对基础进行建模。通用 FEA 工具(如VisualAnalysis)可以做很多事情,但对于特定于基础的工程来说,这更快、更智能。 草图边界 快速绘…...
C++中成员函数的重载覆盖与隐藏
1.重载与覆盖 重载:成员函数被重载的特征:在同一个类中,函数名相同,参数不同,vritual关键字可有可无。 覆盖:覆盖是指派生类函数覆盖基类函数,特征是:在有继承关系的类中࿰…...
电子器件系列49:CD4050B缓冲器
同相和反向缓冲器 还搞不懂缓冲电路?看这一文,工作原理作用电路设计使用方法 - 知乎 (zhihu.com) 缓冲器_百度百科 (baidu.com) 1、缓冲器的定义 缓冲器是数字元件的其中一种,它对输入值不执行任何运算,其输出值和输入值一样&…...
Leetcode 349 两个数组的交集 (哈希表)
Leetcode 349 两个数组的交集 (哈希表) 解法1 😋解法2 解法1 😋 自己的笨比方法:【哇这居然是标准解法之一,我不是笨比😋😋😋】 创建了两个hash数组,nums1出现一个就对应…...
基于YOLOv8模型的水下目标检测系统(PyTorch+Pyside6+YOLOv8模型)
摘要:基于YOLOv8模型的水下目标检测系统可用于日常生活中检测与定位鱼、水母、企鹅、海鹦、鲨鱼、海星、黄貂鱼,利用深度学习算法可实现图片、视频、摄像头等方式的目标检测,另外本系统还支持图片、视频等格式的结果可视化与结果导出。本系统…...
vue-cli脚手架创建项目时报错Error: command failed: npm install --loglevel error
项目背景 环境:vue-cli 5.x 在工程文件中,后端模块wms已经创建完成,现在想新建一个名为vue-web的前端模块 执行命令vue create vue-web时, 报错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的时候,去清华源下载RPM包时发现同一个软件有许多不同架构的安装包,常见的有amd64、x86、x86_64、arm64这些架构&am…...
简单易学,让你拥有个性化的二维码
在数字化时代,二维码已经成为了我们日常生活的一部分。然而,大多数二维码都是简单而乏味的,缺乏个性和吸引力。这篇文章将向你介绍如何使用乔拓云等免费在线海报制作工具来制作艺术二维码,让你轻松掌握二维码的美化技巧。 1. 选择…...
开源原生android的视频编辑软件
videoEditAndroid 介绍 开源原生android的视频编辑软件 本人android 新手,也是边写边学习中,感觉写的很乱,功能虽已实现,但是会不断优化代码 也欢迎有兴趣的小伙伴加入 码农不易,欢迎 star 项目页面功能完成列表 视频选择(待完善) 静音 视频编辑 导…...
10kb的照片尺寸怎么弄?几个步骤轻松搞定!
为了图片方便在互联网上分享、传输或存储,我们常常会有缩小图片的需求,那么如何进行操作呢?下面分享了三种实用的方法。 方法一:使用嗨格式压缩大师 1、在电脑上打开安装好的“嗨格式压缩大师”,在首界面中点击“图片…...
uniapp-vue3-微信小程序-标签选择器wo-tag
采用uniapp-vue3实现, 是一款支持高度自定义的标签选择器组件,支持H5、微信小程序(其他小程序未测试过,可自行尝试) 可到插件市场下载尝试: https://ext.dcloud.net.cn/plugin?id14960 使用示例 <template>&…...
数据结构与算法-(9)---双端队列(Deque)
🌈write in front🌈 🧸大家好,我是Aileen🧸.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流. 🆔本文由Aileen_0v0🧸 原创 CSDN首发🐒 如…...
DTI综述(更新中)
Deep Learning for drug repurposing:methods,datasets,and applications 综述读完,觉得少了点东西,自己写个DTI综述 Databases(包括但不限于文章中的) DATABASEDESCRIBEBindingDB有详细的drug信息和对应的target&a…...
封装一个滑块控制灯光组件
效果如下gif 只进行了基础的事件和布局,可优化的地方:luminance-box这个div加上后,由于和slider-run-way都是absolute定位,导致slider-run-way的点击事件无法设置值,只能通过滑块设置。暂时想不到咋处理,有…...
flutter循环
flutter for循环: 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连接器,向任意类型的关系型数据库读取或者写入数据 添加Maven依赖 <dependency><groupId>org.apache.flink</groupId><artifactId>flink-connector-jdbc</artifactId><version>3.1…...
Flink日志收集到数据库/kafka
引言 我们做项目过程中发现flink日志不同模式启动,存放位置不同,查找任务日志很不方便,具体问题如下: 原始flink的日志配置文件log4j-cli.properties appender.file.append false,取消追加,直接覆盖掉上…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
C++_哈希表
本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说,直接开始吧! 一、基础概念 1. 哈希核心思想: 哈希函数的作用:通过此函数建立一个Key与存储位置之间的映射关系。理想目标:实现…...
Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合
无论是python,或者java 的大型项目中,都会涉及到 自身平台微服务之间的相互调用,以及和第三发平台的 接口对接,那在python 中是怎么实现的呢? 在 Python Web 开发中,FastAPI 和 Django 是两个重要但定位不…...
内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献
Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译: ### 胃肠道癌症的发病率呈上升趋势,且有年轻化倾向(Bray等人,2018&#x…...
