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,取消追加,直接覆盖掉上…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...
高防服务器价格高原因分析
高防服务器的价格较高,主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因: 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器,因此…...
云安全与网络安全:核心区别与协同作用解析
在数字化转型的浪潮中,云安全与网络安全作为信息安全的两大支柱,常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异,并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全:聚焦于保…...
前端开发者常用网站
Can I use网站:一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use:Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站:MDN JavaScript权威网站:JavaScript | MDN...
node.js的初步学习
那什么是node.js呢? 和JavaScript又是什么关系呢? node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说, 需要在node.js的环境上进行当JavaScript作为前端开发语言来说,需要在浏览器的环境上进行 Node.js 可…...
