力扣:438. 找到字符串中所有字母异位词 题解
Problem: 438. 找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词
- 预备知识
- 解题思路
- 复杂度
- Code
- 其它细节
- 推荐博客或题目
- 博客
- 题目
- 滑动窗口
- 哈希表
预备知识

此题用到了双指针算法中的滑动窗口思想,以及哈希表的运用。c++中是unordered_map。如果对此不了解的uu,建议查看相关介绍博客和更简单的题目!!!
解题思路
该题解法为:滑动窗口 + 哈希表。
-
该题的滑动窗口是固定的,我们只需要对每次移动新字符和删除字符进行判断,时间复杂度为O(n)。
-
首先,定义一个哈希表,记录要满足匹配p字符串需要多少的对应的字符。
unordered_map<char, int> pp; -
遍历p,出现对应的字符,就在该位置的–,说明还需要在s中找多少该字符。
while (j < p.size()) { //O(1) 理论上子字符串的操作应该是1//开始遍历,在s上初始化第一个字符串,能够满足对应字符供给的就++pp[s[j++]]++; } -
遍历pp,如果不为0,说明该子字符串不满足匹配条件,则跳到x.
for (auto& [a, b] : pp) { //O(1) max=26//遍历pp,如果不为0,说明该子字符串不满足匹配条件,则跳到xif (b != 0) goto x; } -
最后进行全局遍历
while (j < s.size()) { //O(n)//开始遍历//对于j位置的字符,将pp对应位置++,表示提供一个字符pp[s[j]]++;//对于i位置的字符,将pp对应位置--,表示不能提供一个字符pp[s[i]]--;for (auto& [a, b] : pp) { //O(1) max=26if (b != 0) goto xx;}v.push_back(i + 1);xx:;i++;j++; }
复杂度
时间复杂度:
O(26 * n),26是遍历哈希表中的每种英文字母的个数,最多为26,n是遍历滑动窗口。
空间复杂度:
O(26 + n),26是哈希表最大size,n是vector最大size。
Code
class Solution {
public:vector<int> findAnagrams(string s, string p) {//记录要满足匹配p字符串需要多少的对应的字符unordered_map<char, int> pp; vector<int> v;int i = 0, j = 0;for (auto a : p) { //O(n)//遍历p,出现对应的字符,就在该位置的--,说明还需要多少该字符pp[a]--;}while (j < p.size()) { //O(1) 理论上子字符串的操作应该是1//开始遍历,在s上初始化第一个字符串,能够满足对应字符供给的就++pp[s[j++]]++;}for (auto& [a, b] : pp) { //调试bug的时候可以用输出的方法cout << a << b << endl;}for (auto& [a, b] : pp) { //O(1) max=26//遍历pp,如果不为0,说明该子字符串不满足匹配条件,则跳到xif (b != 0) goto x;}v.push_back(i);x:;while (j < s.size()) { //O(n)//开始遍历//对于j位置的字符,将pp对应位置++,表示提供一个字符pp[s[j]]++;//对于i位置的字符,将pp对应位置--,表示不能提供一个字符pp[s[i]]--;for (auto& [a, b] : pp) { //O(1) max=26if (b != 0) goto xx;}v.push_back(i + 1);xx:;i++;j++;}return v;}
};
其它细节
可以尝试用输出日志的方式来获得局部代码的正确性。对于比较长的代码,我们应该在写完整个代码之前,已经完成多个地方的日志输出。多加练习能够提高自己写代码的正确性。
for (auto& [a, b] : pp) { //调试bug的时候可以用输出的方法cout << a << b << endl;
}
推荐博客或题目
博客
- 滑动窗口详解
- 哈希表理论基础
题目
滑动窗口
- 无重复字符的最长子串 难度:++
哈希表
- 两数之和 难度:++
- 三数之和 难度:+++
- 四数之和 难度:++++
- 四数相和II 难度:++++
相关文章:
力扣:438. 找到字符串中所有字母异位词 题解
Problem: 438. 找到字符串中所有字母异位词 438. 找到字符串中所有字母异位词 预备知识解题思路复杂度Code其它细节推荐博客或题目博客题目滑动窗口哈希表 预备知识 此题用到了双指针算法中的滑动窗口思想,以及哈希表的运用。c中是unordered_map。如果对此不了解的u…...
QT 高DPI解决方案
一、根据DPI实现动态调整控件大小(三种方式) 1、QT支持高DPI(针对整个进程中所有的UI) // main函数中 QApplication::setAttribute(Qt::AA_EnableHighDpiScaling)tips:(1)如果不想全局设置&am…...
SLB、DMZ、Nginx、Ingress、Gateway、Kibana和Grafana
SLB、DMZ、Nginx、Ingress、Gateway、Kibana和Grafana虽然有一些相似之处,但是它们的功能和适用场景还是有所不同。 SLB主要用于将大流量的请求分配到多个服务器上进行处理,从而提高系统的可伸缩性和可靠性。它适用于需要处理大流量的应用,如…...
【已解决】Invalid bound statement (not found)
报错讯息 org.apache.ibatis.binding.BindingException: Invalid bound statement (not found): com.casey.mapper.SysRoleMapper.getUserRoleCode at org.apache.ibatis.binding.MapperMethod S q l C o m m a n d . < i n i t > ( M a p p e r M e t h o d . j a v a :…...
汽车信息安全--芯片厂、OEM安全启动汇总(1)
目录 1.芯驰E3安全启动 2.STM32 X-CUBE-SBSFU 3.小米澎湃OS安全启动 4.小结 我在前篇文章里详细记录了车规MCU信息安全设计过程关于网络安全架构的思考过程,从芯片原厂、供应商、OEM等角度思考如何建立起完备的信任链; 不过这思考过程仅仅只是一家之言,因此我又对比了国…...
气膜建筑:舒适、智能、可持续
气膜建筑之所以能够拥有广阔的发展空间,源于其融合了诸多优势特点,使其成为未来建筑领域的前沿趋势。 气膜建筑注重环境可持续性和能源效率。在材料和设计上,它采用可回收材料、提高热保温效果,并积极利用太阳能等可再生能源&…...
【C语言】一种状态超时阻塞循环查询的办法
【C语言】一种状态超时阻塞循环查询的办法 文章目录 【C语言】一种状态超时阻塞循环查询的办法1.方法12.方法21.方法1 static void wait_notify_async(notify_type_t notify_type) {static rt_tick_t exit_tick;exit_tick = rt_time_get_msec();lb_int32 notify_success = RT_F…...
【leetcode】力扣热门之回文链表【简单难度】
题目描述 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 用例 输入:head [1,2,2,1] 输出:true 输入:head [1,2] 输出:f…...
【MySQL】ALL函数的巧用 以及 排序(order by)巧用 sum(条件表达式) 语法
力扣题 1、题目地址 578. 查询回答率最高的问题 2、模拟表 SurveyLog 表: Column NameTypeidintactionENUMquestion_idintanswer_idintq_numinttimestampint 这张表可能包含重复项。action 是一个 ENUM(category) 数据,可以是 “show”、“answer”…...
Debezium发布历史49
原文地址: https://debezium.io/blog/2019/02/19/reliable-microservices-data-exchange-with-the-outbox-pattern/ 欢迎关注留言,我是收集整理小能手,工具翻译,仅供参考,笔芯笔芯. 使用发件箱模式进行可靠的微服务数…...
数据结构——队列(Queue)
目录 1.队列的介绍 2.队列工程 2.1 队列的定义 2.1.1 数组实现队列 2.1.2 单链表实现队列 2.2 队列的函数接口 2.2.1 队列的初始化 2.2.2 队列的数据插入(入队) 2.2.3 队列的数据删除(出队) 2.2.4 取队头数据 2.2.5 取队…...
uniapp微信小程序投票系统实战 (SpringBoot2+vue3.2+element plus ) -后端架构搭建
锋哥原创的uniapp微信小程序投票系统实战: uniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )_哔哩哔哩_bilibiliuniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )共计21条视频…...
两种方式实现mysql截取年月日
select date_format(now(), %Y-%m-%d) select substring(now(), 1, 10)...
WPF 使用矢量字体图标
矢量字体图标 在WPF项目中经常需要显示图标,但是项目改动后,有时候需要替换和修改图标,这样非常麻烦且消耗开发和美工的时间。为了快速开发项目,节省项目时间,使用图标矢量字体图标是一个非常不错的选择。 矢量字体图标…...
编程语言的语法糖,你了解多少?
什么是语法糖 语法糖是一种编程语言的特性,通常是一些简单的语法结构或函数调用,它可以通过隐藏底层的复杂性,并提供更高级别的抽象,从而使代码更加简洁、易读和易于理解,但它并不会改变代码的执行方式。 为什么需要语…...
MySQL中FLUSH TABLES命令语法
在MySQL中,FLUSH TABLES 命令的作用是刷新表。当你使用 FLUSH TABLES 命令的具体选项时(例如 FLUSH TABLES WITH READ LOCK),该选项必须是在 FLUSH 语句中唯一指定的命令。即,在一个 FLUSH 语句中,你只能使…...
如何在小米4A刷OpenWRT系统并通过cpolar实现公网访问本地路由器
文章目录 前言1. 安装Python和需要的库2. 使用 OpenWRTInvasion 破解路由器3. 备份当前分区并刷入新的Breed4. 安装cpolar内网穿透4.1 注册账号4.2 下载cpolar客户端4.3 登录cpolar web ui管理界面4.4 创建公网地址 5. 固定公网地址访问 前言 OpenWRT是一个高度模块化、高度自…...
Spring学习之——事务控制
Spring中的事务控制 说明: JavaEE体系进行分层开发,事务处理位于业务层,Spring提供了分层设计业务层的事务处理解决方案。 Spring框架为我们提供了一组事务控制的接口。具体在后面的小节介绍。这组接口是在spring-tx.RELEASE.jar中。 spri…...
云原生技术专题 | 解密2023年云原生的安全优化升级,告别高危漏洞、与数据泄露说“再见”(安全管控篇)
背景介绍 2023年,我们见证了科技领域的蓬勃发展,每一次技术革新都为我们带来了广阔的发展前景。作为后端开发者,我们深受其影响,不断迈向未来。 随着数字化浪潮的席卷,各种架构设计理念相互交汇,共同塑造了…...
如何启用Windows电脑的内置Administrator账户
前言 不知道从什么时候开始,新电脑或者新系统开机之后都会出现一个界面让你创建一个账户,但这个账户有可能是本地账户(Windows10)还有强制你登录微软账户的(Windows11)。 好像曾经熟悉的电脑Administrator…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
CMS内容管理系统的设计与实现:多站点模式的实现
在一套内容管理系统中,其实有很多站点,比如企业门户网站,产品手册,知识帮助手册等,因此会需要多个站点,甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...
大模型真的像人一样“思考”和“理解”吗?
Yann LeCun 新研究的核心探讨:大语言模型(LLM)的“理解”和“思考”方式与人类认知的根本差异。 核心问题:大模型真的像人一样“思考”和“理解”吗? 人类的思考方式: 你的大脑是个超级整理师。面对海量信…...
uniapp获取当前位置和经纬度信息
1.1. 获取当前位置和经纬度信息(需要配置高的SDK) 调用uni-app官方API中的uni.chooseLocation(),即打开地图选择位置。 <button click"getAddress">获取定位</button> const getAddress () > {uni.chooseLocatio…...
自定义线程池1.2
自定义线程池 1.2 1. 简介 上次我们实现了 1.1 版本,将线程池中的线程数量交给使用者决定,并且将线程的创建延迟到任务提交的时候,在本文中我们将对这个版本进行如下的优化: 在新建线程时交给线程一个任务。让线程在某种情况下…...
