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

【算法学习】-【滑动窗口】-【找到字符串中所有字母异位词】

LeetCode原题链接:438. 找到字符串中所有字母异位词

下面是题目描述:
给定两个字符串 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、解题思路
前言:如果有第一次学习滑动窗口算法的朋友,可以先阅读一下笔者关于滑动窗口算法的第一篇文章:【算法学习】-【滑动窗口】-【长度最小的子数组】,那里对滑动窗口会有较详细的讲解,下面的解题思路中关于相关算法的步骤就仅进行简单的叙述啦。

由题目描述可得, 本题主要可分为以下两个步骤:
(1)判断一个字符串是否为另一个字符串的异位词
这里需要借助哈希表这个数据结构来进行判断,即将两个字符串中的字符分别放入两个哈希表中,然后对比这两个哈希表,若两个哈希表中的字符及字符个数都一样,则说明是异位词;否则不是。

(2)确定滑动窗口
相较于之前笔者有关滑动窗口算法的文章中的滑动窗口,这里的窗口大小是恒定的,即用于构成窗口大小的两个指针是 “共进退” 的。故此时直接照搬之前控制窗口移动的思路反而会使情况变得复杂。下面介绍一下算法的步骤

  • 先初始化两个哈希表,便于直接进行第一次判断
  • 判断两个哈希表中的内容否相等,若相等,则记录索引(也就是构成窗口的前面的那个指针的值)
  • 接着无论是否相等都需将字符串s对应的哈希表中的第一个字符删除(注意这里要先让数量--,数量为0后才执行删除操作)而进行下一次枚举
  • 删除后,向s对应的哈希表中插入新的字符,然后两个指针都向后移动一位,准备进行下一次的判断。循环执行上述过程。

2、具体代码

 	vector<int> findAnagrams(string s, string p){unordered_map<char, int> mapOfp;unordered_map<char, int> mapOfs;//初始化哈希表for (size_t i = 0; i < p.size(); i++){mapOfp[p[i]]++;mapOfs[s[i]]++;}vector<int> res;size_t cur = p.size();size_t begin = 0;while (cur <= s.size()){if (mapOfp == mapOfs){res.push_back(begin);}if( --mapOfs[s[begin]] == 0){mapOfs.erase(s[begin]);}begin++;mapOfs[s[cur++]]++;}if (mapOfp == mapOfs){res.push_back(begin);}return res;}

看完觉得有觉得帮助的话不妨点赞收藏鼓励一下,有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论,多多指点,谢谢朋友们!🌹🌹🌹

相关文章:

【算法学习】-【滑动窗口】-【找到字符串中所有字母异位词】

LeetCode原题链接&#xff1a;438. 找到字符串中所有字母异位词 下面是题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找到 s 中所有 p 的 异位词 的子串&#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串&…...

利用python学习如何处理需要登录的网站

要处理需要登录的网站&#xff0c;你可以按照以下步骤进行学习&#xff1a; 了解网站的登录机制&#xff1a;登录机制通常有用户名密码登录、OAuth授权登录、Cookie登录等。了解目标网站使用的登录机制是学习处理的第一步。 使用Web抓取工具模拟登录&#xff1a;通过使用工具如…...

vue适配各个屏幕

1:不是响应式&#xff0c;只是用缩放来适配各个pc 2&#xff1a;使用中会出现由于 transform 属性导致的定位问题&#xff0c;具体的需要针对性的处理 App.vue <div id"app" ><div class"app-view" :style"{--scale:scale}"><…...

在conda创建的虚拟环境中安装jupyter以及使用

1. 进入你的虚拟环境 conda activate conda_env_name 2. 安装jupyter notebook conda install -y jupyter 3. 启动jupyter jupyter notebook 4. 将conda环境添加到jupyter的内核中 conda install ipykernel python -m ipykernel install --name conda_env_namepython -m…...

【Java 8的新特性】

引言 Java 8是Java编程语言的一个重要里程碑&#xff0c;它引入了许多令人兴奋的新特性和改进。这些新特性不仅使Java编程更加简洁和高效&#xff0c;还提供了更多的功能和灵活性。在本文中&#xff0c;我们将探讨Java 8的一些重要新特性&#xff0c;并展示它们是如何改变我们…...

Android+Appium自动化测试环境搭建及实操

1、Appium简介1.1 Appium概念1.2 Appium工作原理 2、Appium Server环境搭建2.1 Java JDK2.1.1 下载JDK2.1.2 运行exe安装JDK&#xff0c;设置安装路径2.1.3 设置环境变量2.1.4 验证安装结果 2.2 Android SDK2.2.1 下载安装Android SDK安装包2.2.2 下载platform-tools&#xff0…...

NetSuite ERP系统健康检查

这个题目来自最近的一个项目感受&#xff0c;“上线即停滞”。这是在中小型企业十分普遍的一个情况&#xff0c;一旦上线后&#xff0c;基本上信息化的建设就停止了。这是一个中小企业信息化的一个特点&#xff0c;因为其IT力量比较弱&#xff0c;所以在信息化的推动中缺乏话语…...

常用的数字格式代码

文章目录 数值占位符文本占位符 两类占位符: 数值占位符, 文本占位符. 数值占位符 有三种&#xff1a;0&#xff0c;#&#xff0c;&#xff1f; 0 是强制的占位符。 文本占位符 文本占位符只有一个&#xff1a; : 作用于文本的占位符&#xff0c;可以用英文引号" &quo…...

GitLab使用步骤

GitLab使用步骤 1 注册用户 1 访问&#xff1a;http://10.0.0.203/users/sign_up地址 2 填入注册信息&#xff0c;注册成功&#xff0c;需要管理员审核 3 用root登录&#xff0c;地址&#xff1a;http://10.0.0.203/users/sign_in账号&#xff1a;root密码&#xff1a;xxxx…...

基于MindSpore的llama微调在OpenI平台上运行

基于MindSpore的llama微调在OpenI平台上运行 克隆预训练模型 克隆chatglm-6b代码仓&#xff0c;下载分布式的模型文件 git lfs install git clone https://huggingface.co/openlm-research/open_llama_7b准备环境 安装Transformer pip install transformers执行转换脚本 …...

P34~36第八章相量法

8.1复数 复数可表示平面矢量、也可表示正弦量。特别是: 当复数表示正弦量的时候&#xff0c;此时复数称为相量。 8.2复数运算 复数除法也可看做乘法&#xff0c;乘法的几何意义是旋转&#xff08;辐角相加&#xff09;( e^x e^y e^xy)&#xff0c;同时伸缩&#xff08;模变…...

WAF绕过-漏洞发现之代理池指纹探针 47

工具 工具分为综合性的&#xff0c;有awvs&#xff0c;xray&#xff0c;单点的比如wpscan专门扫描wordpress的。而我们使用工具就可能会触发waf&#xff0c; 触发点 第一个就是扫描速度&#xff0c;太快了&#xff0c;可以通过演示&#xff0c;开代理池&#xff0c;白名单绕…...

模型预测控制(MPC)中考虑约束中的不确定性(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

校招C#面试题整理—Unity客户端

前言 博客已经1年多没有更新了&#xff0c;这一年主要在实习并准备秋招和春招&#xff0c;目前已经上岸Unity客户端岗位&#xff0c;现将去年校招遇到的一些面试题的事后整理分享出来。答案是笔者自己整理的不一定保证准确&#xff0c;欢迎大家在评论区指出。 Unity客户端岗的…...

【数字IC设计】利用Design Compiler评估动态功耗

利用DC对RTL设计的动态功耗进行评估,主要可以分为以下步骤: 用vcs编译运行testbench,生成.saif文件(Switching Activity Interchange Format)在Design Compiler编译前,读入.saif文件Design Compiler编译完设计文件后,输出功耗报告 下面通过一个计数器的设计,来演示该过程…...

Docker Compose命令讲解+文件编写

docker compose的用处是对 Docker 容器集群的快速编排。&#xff08;源码&#xff09; 一个 Dockerfile 可以定义一个单独的应用容器。但我们经常碰到需要多个容器相互配合来完成某项任务的情况&#xff08;如实现一个 Web 项目&#xff0c;需要服务器、数据库、redis等&#…...

Linux bash: ipconfig: command not found解决方法

安装完centos7运行ifconfig命令发现找不到 安装相关工具 yum install net-tools.x86_64 无脑yes即可...

【面试算法——动态规划 21】正则表达式匹配(hard) 交错字符串

10. 正则表达式匹配 链接: 10. 正则表达式匹配 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素 所谓匹配&#xff0c;是要涵盖 整个 字符串 s的&#xf…...

基于Python实现的神经网络分类MNIST数据集

神经网络分类MNIST数据集 目录 神经网络分类MNIST数据集 1 一 、问题背景 1 1.1 神经网络简介 1 前馈神经网络模型&#xff1a; 1 1.2 MINST 数据说明 4 1.3 TensorFlow基本概念 5 二 、实现说明 5 2.1 构建神经网络模型 5 为输入输出分配占位符 5 搭建分层的神经网络 6 处理预…...

设计模式之是简单工厂模式

分类 设计模式一般分为三大类&#xff1a;创建型模式、结构型模式、行为型模式。 创建型模式&#xff1a;用于创建对象&#xff0c;共五种&#xff0c;包括单例模式、简单工厂模式、工厂方法模式、抽象工厂模式、建造者模式、原型模式。结构型模式&#xff1a;用于处理类或对…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...

VASP软件在第一性原理计算中的应用-测试GO

VASP软件在第一性原理计算中的应用 VASP是由维也纳大学Hafner小组开发的一款功能强大的第一性原理计算软件&#xff0c;广泛应用于材料科学、凝聚态物理、化学和纳米技术等领域。 VASP的核心功能与应用 1. 电子结构计算 VASP最突出的功能是进行高精度的电子结构计算&#xff…...

多模态大语言模型arxiv论文略读(112)

Assessing Modality Bias in Video Question Answering Benchmarks with Multimodal Large Language Models ➡️ 论文标题&#xff1a;Assessing Modality Bias in Video Question Answering Benchmarks with Multimodal Large Language Models ➡️ 论文作者&#xff1a;Jea…...