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

力扣:438. 找到字符串中所有字母异位词 题解

Problem: 438. 找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词

  • 预备知识
  • 解题思路
  • 复杂度
  • Code
  • 其它细节
  • 推荐博客或题目
    • 博客
    • 题目
      • 滑动窗口
      • 哈希表

预备知识

image.png

此题用到了双指针算法中的滑动窗口思想,以及哈希表的运用。c++中是unordered_map。如果对此不了解的uu,建议查看相关介绍博客和更简单的题目!!!

解题思路

该题解法为:滑动窗口 + 哈希表。

  1. 该题的滑动窗口是固定的,我们只需要对每次移动新字符和删除字符进行判断,时间复杂度为O(n)。

  2. 首先,定义一个哈希表,记录要满足匹配p字符串需要多少的对应的字符。

    unordered_map<char, int> pp;
    
  3. 遍历p,出现对应的字符,就在该位置的–,说明还需要在s中找多少该字符。

    while (j < p.size()) {  //O(1) 理论上子字符串的操作应该是1//开始遍历,在s上初始化第一个字符串,能够满足对应字符供给的就++pp[s[j++]]++;
    }
    
  4. 遍历pp,如果不为0,说明该子字符串不满足匹配条件,则跳到x.

    for (auto& [a, b] : pp) {   //O(1) max=26//遍历pp,如果不为0,说明该子字符串不满足匹配条件,则跳到xif (b != 0) goto x;
    }
    
  5. 最后进行全局遍历

    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;
}

推荐博客或题目

博客

  1. 滑动窗口详解
  2. 哈希表理论基础

题目

滑动窗口

  1. 无重复字符的最长子串 难度:++

哈希表

  1. 两数之和 难度:++
  2. 三数之和 难度:+++
  3. 四数之和 难度:++++
  4. 四数相和II 难度:++++

相关文章:

力扣:438. 找到字符串中所有字母异位词 题解

Problem: 438. 找到字符串中所有字母异位词 438. 找到字符串中所有字母异位词 预备知识解题思路复杂度Code其它细节推荐博客或题目博客题目滑动窗口哈希表 预备知识 此题用到了双指针算法中的滑动窗口思想&#xff0c;以及哈希表的运用。c中是unordered_map。如果对此不了解的u…...

QT 高DPI解决方案

一、根据DPI实现动态调整控件大小&#xff08;三种方式&#xff09; 1、QT支持高DPI&#xff08;针对整个进程中所有的UI&#xff09; // main函数中 QApplication::setAttribute(Qt::AA_EnableHighDpiScaling)tips&#xff1a;&#xff08;1&#xff09;如果不想全局设置&am…...

SLB、DMZ、Nginx、Ingress、Gateway、Kibana和Grafana

SLB、DMZ、Nginx、Ingress、Gateway、Kibana和Grafana虽然有一些相似之处&#xff0c;但是它们的功能和适用场景还是有所不同。 SLB主要用于将大流量的请求分配到多个服务器上进行处理&#xff0c;从而提高系统的可伸缩性和可靠性。它适用于需要处理大流量的应用&#xff0c;如…...

【已解决】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等角度思考如何建立起完备的信任链; 不过这思考过程仅仅只是一家之言,因此我又对比了国…...

气膜建筑:舒适、智能、可持续

气膜建筑之所以能够拥有广阔的发展空间&#xff0c;源于其融合了诸多优势特点&#xff0c;使其成为未来建筑领域的前沿趋势。 气膜建筑注重环境可持续性和能源效率。在材料和设计上&#xff0c;它采用可回收材料、提高热保温效果&#xff0c;并积极利用太阳能等可再生能源&…...

【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 &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 用例 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true 输入&#xff1a;head [1,2] 输出&#xff1a;f…...

【MySQL】ALL函数的巧用 以及 排序(order by)巧用 sum(条件表达式) 语法

力扣题 1、题目地址 578. 查询回答率最高的问题 2、模拟表 SurveyLog 表&#xff1a; Column NameTypeidintactionENUMquestion_idintanswer_idintq_numinttimestampint 这张表可能包含重复项。action 是一个 ENUM(category) 数据&#xff0c;可以是 “show”、“answer”…...

Debezium发布历史49

原文地址&#xff1a; https://debezium.io/blog/2019/02/19/reliable-microservices-data-exchange-with-the-outbox-pattern/ 欢迎关注留言&#xff0c;我是收集整理小能手&#xff0c;工具翻译&#xff0c;仅供参考&#xff0c;笔芯笔芯. 使用发件箱模式进行可靠的微服务数…...

数据结构——队列(Queue)

目录 1.队列的介绍 2.队列工程 2.1 队列的定义 2.1.1 数组实现队列 2.1.2 单链表实现队列 2.2 队列的函数接口 2.2.1 队列的初始化 2.2.2 队列的数据插入&#xff08;入队&#xff09; 2.2.3 队列的数据删除&#xff08;出队&#xff09; 2.2.4 取队头数据 2.2.5 取队…...

uniapp微信小程序投票系统实战 (SpringBoot2+vue3.2+element plus ) -后端架构搭建

锋哥原创的uniapp微信小程序投票系统实战&#xff1a; uniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )_哔哩哔哩_bilibiliuniapp微信小程序投票系统实战课程 (SpringBoot2vue3.2element plus ) ( 火爆连载更新中... )共计21条视频…...

两种方式实现mysql截取年月日

select date_format(now(), %Y-%m-%d) select substring(now(), 1, 10)...

WPF 使用矢量字体图标

矢量字体图标 在WPF项目中经常需要显示图标&#xff0c;但是项目改动后&#xff0c;有时候需要替换和修改图标&#xff0c;这样非常麻烦且消耗开发和美工的时间。为了快速开发项目&#xff0c;节省项目时间&#xff0c;使用图标矢量字体图标是一个非常不错的选择。 矢量字体图标…...

编程语言的语法糖,你了解多少?

什么是语法糖 语法糖是一种编程语言的特性&#xff0c;通常是一些简单的语法结构或函数调用&#xff0c;它可以通过隐藏底层的复杂性&#xff0c;并提供更高级别的抽象&#xff0c;从而使代码更加简洁、易读和易于理解&#xff0c;但它并不会改变代码的执行方式。 为什么需要语…...

MySQL中FLUSH TABLES命令语法

在MySQL中&#xff0c;FLUSH TABLES 命令的作用是刷新表。当你使用 FLUSH TABLES 命令的具体选项时&#xff08;例如 FLUSH TABLES WITH READ LOCK&#xff09;&#xff0c;该选项必须是在 FLUSH 语句中唯一指定的命令。即&#xff0c;在一个 FLUSH 语句中&#xff0c;你只能使…...

如何在小米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中的事务控制 说明&#xff1a; JavaEE体系进行分层开发&#xff0c;事务处理位于业务层&#xff0c;Spring提供了分层设计业务层的事务处理解决方案。 Spring框架为我们提供了一组事务控制的接口。具体在后面的小节介绍。这组接口是在spring-tx.RELEASE.jar中。 spri…...

云原生技术专题 | 解密2023年云原生的安全优化升级,告别高危漏洞、与数据泄露说“再见”(安全管控篇)

背景介绍 2023年&#xff0c;我们见证了科技领域的蓬勃发展&#xff0c;每一次技术革新都为我们带来了广阔的发展前景。作为后端开发者&#xff0c;我们深受其影响&#xff0c;不断迈向未来。 随着数字化浪潮的席卷&#xff0c;各种架构设计理念相互交汇&#xff0c;共同塑造了…...

如何启用Windows电脑的内置Administrator账户

前言 不知道从什么时候开始&#xff0c;新电脑或者新系统开机之后都会出现一个界面让你创建一个账户&#xff0c;但这个账户有可能是本地账户&#xff08;Windows10&#xff09;还有强制你登录微软账户的&#xff08;Windows11&#xff09;。 好像曾经熟悉的电脑Administrator…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...

动态规划-1035.不相交的线-力扣(LeetCode)

一、题目解析 光看题目要求和例图&#xff0c;感觉这题好麻烦&#xff0c;直线不能相交啊&#xff0c;每个数字只属于一条连线啊等等&#xff0c;但我们结合题目所给的信息和例图的内容&#xff0c;这不就是最长公共子序列吗&#xff1f;&#xff0c;我们把最长公共子序列连线起…...

FTXUI::Dom 模块

DOM 模块定义了分层的 FTXUI::Element 树&#xff0c;可用于构建复杂的终端界面&#xff0c;支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...

P10909 [蓝桥杯 2024 国 B] 立定跳远

# P10909 [蓝桥杯 2024 国 B] 立定跳远 ## 题目描述 在运动会上&#xff0c;小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1, a_2, \cdots , a_n$ 且 $a_i \ge a_{i−1} > 0$。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时&#xff0…...