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

LeetCode 热题 100——找到字符串中所有字母异位词(滑动窗口)

题目链接

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目解析

该题目的意思简而言之就是说,从s字符串中寻找与p字符串含有相同字符(次数和种类均相同)的子串,并且将他们的首字符下标集合进数组中进行返回。

滑动窗口解法(未优化版本)

分析完该题目可以发现,该题是一个大小不变的滑动窗口题目。窗口大小一直为p字符串的大小,并且我们出窗口和进窗口的大小是相同的,就相当于我们拿着一个窗口在s字符串上去滑动,直到我们找到合适的子串。

如以下动图所示:

 代码如下(含详细注释)

// 该题是一个大小固定的滑动窗口题目
class Solution 
{
public:// 设计一个函数来检查两个哈希表是否相等bool check_hash(int hash1[],int hash2[]){for(int i=0;i<26;i++)if(hash1[i]!=hash2[i]) return false;return true;}vector<int> findAnagrams(string s, string p) {int p_hash[26]={0};int s_hash[26]={0};int ns=s.size();int np=p.size();// 将p字符串中的字符插入到p_hash中for(auto&e:p) p_hash[e-'a']++;vector<int> ret;for(int left=0,right=0;right<ns;right++){// 直接将right对应位置字符进行入哈希表char in=s[right];s_hash[in-'a']++;// 如果right-left+1>np说明已经超过我们滑动窗口的大小了if(right-left+1>np){// 直接从左边进行出窗口char out=s[left++];s_hash[out-'a']--;}// 检查是否符合条件(两个哈希表是否相等)if(check_hash(s_hash,p_hash))// 相等就把该字符串最左边字符的下标入ret数组中ret.push_back(left);}return ret;}
};

滑动窗口(优化版本)

该题只存放了小写字母,因此我们检查两个哈希表其实时间复杂度是非常低的,倘若存入的不止是小写字母,那么我们检查的这一步操作时间复杂度就会非常高,并且检查的这一步操作每一次滑动的时候我们都要进行检测,因此我们可以使用一个count来记录s_hash哈希表中有效字符(存在的字符是p_hash中的字符)的数量,进窗口的时候我们将count++,出窗口的时候我们将count--。

代码如下(含详细注释)

// 优化版本
// 该题是一个大小固定的滑动窗口题目
class Solution 
{
public:vector<int> findAnagrams(string s, string p) {int p_hash[26]={0};int s_hash[26]={0};int ns=s.size();int np=p.size();// 将p字符串中的字符插入到p_hash中for(auto&e:p) p_hash[e-'a']++;vector<int> ret;for(int left=0,right=0,count=0;right<ns;right++){char in=s[right];// 当前字符插入s_hash之后// 如果s_hash中该字符对应的次数<=p_hash[in-'a']// 说明若不是该字符次数在s_hash中的次数与p_hash中的次数一样// 那就是插入之后还比p_hash中的次数少// 无论哪种情况均能说明该字符存在于p_hash中 符合我们要找的字符// 因此count++ 也就是统计的是s_hash中的有效字符数量if(++s_hash[in-'a']<=p_hash[in-'a']) count++;// 如果right-left+1>np说明已经超过我们滑动窗口的大小了if(right-left+1>np){char out=s[left++];// 这一步同理上一步 // 当我们将该字符移除之前该字符次数在s_hash中小于p_hash// 说明该字符是有效字符// 就算该字符不是我们要的有效字符 仍然可以出窗口 只不过count不进行--操作罢了if(s_hash[out-'a']--<=p_hash[out-'a']) count--;}// 如果此时count==np说明当前情况完全满足我们的要求 加入该结果即可if(count==np)ret.push_back(left);}return ret;}
};

相关文章:

LeetCode 热题 100——找到字符串中所有字母异位词(滑动窗口)

题目链接 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目解析 该题目的意思简而言之就是说&#xff0c;从s字符串中寻找与p字符串含有相同字符(次数和种类均相同)的子串&#xff0c;并且将他们的首字符下标集合进数组中进行返回。 滑动窗口解…...

uniapp从零到一的学习商城实战

涵盖的功能&#xff1a; 安装开发工具HBuilder&#xff1a;HBuilderX-高效极客技巧 创建项目步骤&#xff1a; 1.右键-项目&#xff1a; 2.选择vue2和默认模板&#xff1a; 3.完整的项目目录&#xff1a; 微信开发者工具调试&#xff1a; 1.安装微信开发者工具 2.打开…...

应广单片机实现跑马灯

应广单片机处处体现其mini的特性&#xff0c;非常适合做各种方案开发&#xff0c;特别是点灯&#xff0c;什么跑马灯&#xff0c;氛围灯&#xff0c;遥控灯&#xff0c;感应灯&#xff0c;拍拍灯等&#xff0c;用应广都OK。 跑马灯是基础中的基础&#xff0c;我搭了一个框架&am…...

关于el-input和el-select宽度不一致问题解决

1. 情景一 单列布局 对于上图这种情况&#xff0c;只需要给el-select加上style"width: 100%"即可&#xff0c;如下&#xff1a; <el-select v-model"fjForm.region" placeholder"请选择阀门类型" style"width: 100%"><el-o…...

【Unity3D赛车游戏优化篇】【八】汽车实现镜头的流畅跟随,以及不同角度的切换

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…...

VScode连接远程JupyterNotebook显示点云ply文件

1. remote ssh的配置文件config中添加 Host Jupyter-ServerHostName <IP>ForwardX11 yesForwardX11Trusted yesForwardAgent yesUser <Username> 2. 在远程服务器的.sshd_config中把X11forward的开关打开为yes 3. 在home文件夹中更改.bashrc&#xff0c;加入以下…...

python安装wind10

一、下载&#xff1a; 官网:Python Releases for Windows | Python.org 二、安装 双击下载的安装程序文件。这将打开安装向导。安装界面图下方两个框的" Use admin privileges wheninstalling py. exe和” Add python. exe to PATH"都要勾选,一定要勾选!一定要勾选…...

uni-app 中 swiper 轮播图高度自适应

方法一 1、首先 swiper 标签的宽度是 width: 100% 2、swiper 标签存在默认高度是 height: 150px &#xff1b;高度无法实现由内容撑开&#xff0c;在默认情况下&#xff0c;图片的高度显示总是 150px swiper 宽度 / swiper 高度 原图宽度 / 原图高度 swiper 高度 swiper …...

开源风雷CFD软件多物理场耦合接口开发路线分享!!!

本文将基于开发过程中积累的经验&#xff0c;介绍风雷如何基于preCICE开发适配器。 preCICE是一个开源的多物理场数值模拟耦合库&#xff0c;可以用于多个求解器联合求解一个复杂的多场问题&#xff0c;支持在大规模并行系统上应用&#xff0c;具有良好的并行效率。并且可以对…...

浅谈Mysql读写分离的坑以及应对的方案 | 京东云技术团队

一、主从架构 为什么我们要进行读写分离&#xff1f;个人觉得还是业务发展到一定的规模&#xff0c;驱动技术架构的改革&#xff0c;读写分离可以减轻单台服务器的压力&#xff0c;将读请求和写请求分流到不同的服务器&#xff0c;分摊单台服务的负载&#xff0c;提高可用性&a…...

最近在对接电商供应链,说说开放平台API接口

B2B电商开放平台的设计需要从以下几面去思考&#xff1a; 开放平台API接口的设计&#xff0c;主要是从功能需求的角度&#xff0c;设计满足业务需求的接口及对应的字段&#xff1b; 平台与商家之间信息的对接&#xff0c;对接的方法有哪些&#xff1f;对接过程中需要可能会遇到…...

【FusionInsight 迁移】HBase从C50迁移到6.5.1(02)C50上准备FTP Server

【FusionInsight 迁移】HBase从C50迁移到6.5.1&#xff08;02&#xff09;C50上准备FTP Server HBase从C50迁移到6.5.1&#xff08;02&#xff09;C50上准备FTP Server登录老集群FusionInsight C50的Manager准备FTP User准备FTP Server HBase从C50迁移到6.5.1&#xff08;02&am…...

Java操作符学习笔记

1、布尔类型的逻辑操作符和按位操作符 & 和 &&、|| 和 | 其实是两种操作符。在使用逻辑判断时&#xff0c;有时不希望产生短路作用&#xff0c;会对两个布尔类型值使用单个的 & 或 |运算。这让我一直将单个 & 和 | 当成时逻辑操作符的一种&#xff0c;而事…...

【STM32】学习笔记-PWR(Power Control)电源控制

PWR&#xff08;Power Control&#xff09;电源控制 PWR&#xff08;Power Control&#xff09;电源控制是一种技术或设备&#xff0c;用于控制电源的开关和输出。它通常用于电源管理和节能&#xff0c;可以通过控制电源的工作状态来延长电子设备的使用寿命&#xff0c;减少能…...

安卓 MeasureCache优化了什么?

安卓绘制原理概览_油炸板蓝根的博客-CSDN博客 搜了一下&#xff0c;全网居然没有人提过 measureCache。 在前文中提到过&#xff0c;measure的时候&#xff0c;如果命中了 measureCache&#xff0c;会跳过 onMeasure&#xff0c;同时会设置 PFLAG3_MEASURE_NEEDED_BEFORE_LAYOU…...

docker save docker export 区别

docker save用于导出镜像到文件&#xff0c;包含镜像元数据和历史信息&#xff1b;docker export用于将当前容器状态导出至文件&#xff0c;类似快照&#xff0c;所以不包含元数据及历史信息&#xff0c;体积更小&#xff0c;此外从容器快照导入时也可以重新指定标签和元数据信…...

音频基础知识

文章目录 前言一、音频基本概念1、音频的基本概念①、声音的三要素②、音量与音调③、几个基本概念④、奈奎斯特采样定律 2、数字音频①、采样②、量化③、编码④、其他相关概念<1>、采样位数<2>、通道数<3>、音频帧<4>、比特率&#xff08;码率&#…...

TensorFlow(R与Python系列第四篇)

目录 一、TensorFlow介绍 二、张量 三、有用的TensorFlow运算符 四、reduce系列函数实现约减 1-第一种理解方式&#xff1a;引入轴概念后直观可理 2-第二种理解方式&#xff1a;按张量括号层次的方式 参考&#xff1a; 一、TensorFlow介绍 TensorFlow是一个强大的用于数…...

华为数通方向HCIP-DataCom H12-821题库(单选题:261-280)

第261题 以下关于IPv6过渡技术的描述,正确的是哪些项? A、转换技术的原理是将IPv6的头部改写成IPv4的头部,或者将IPv4的头部改写成IPv6的头部 B、使用隧道技术,能够将IPv4封装在IPv6隧道中实现互通,但是隧道的端点需要支持双栈技术 C、转换技术适用于纯IPv4网络与纯IPv…...

论文《基于概率标签估计的半监督日志缺陷检测》翻译

论文《Semi-supervised Log-based Anomaly Detection via Probabilistic Label Estimation》翻译 Semi-supervised Log-based Anomaly Detection via Probabilistic Label Estimation翻译...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

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

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

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

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

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

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...