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

给定两个字符串 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 * 104
  • s 和 p 仅包含小写字母

题解

一开始是想用两层循环,先将p排序一次,然后将s中每个和p一样长的子串拿出来重新排序之后和p比较是否相同,但是这种做法会超时

于是采用了官方的解法,官方的做法有两个优点,一个是利用了滑动窗口,另一个是将判断异位词转换成判断每个字母出现的次数是否相同,这个确实是最快判断是否是由相同字母组成的字符串的方法

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int>answer;
        int sLength=s.size(),pLength=p.size();
        if(sLength<pLength){ // 如果s短于p,后面无法放置窗口
            return {};
        }
        vector<int>ss(26),pp(26); // 记录字母出现次数
        for(int i=0;i<pLength;i++){ // 放置滑动窗口
            ss[s[i]-'a']++;
            pp[p[i]-'a']++;
        }
        if(ss==pp)
            answer.emplace_back(0);
        for(int i=0;i<sLength-pLength;i++){
            ss[s[i]-'a']--; // 滑动窗口移动,去掉前一个字母的状态
            ss[s[i+pLength]-'a']++; // 滑动窗口移动,增加后一个字母的状态
            if(ss==pp)
                answer.emplace_back(i+1);
        }
        return answer;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/235676.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

运营商二要素API:验证姓名和手机号码一致性的关键工具

前言 在当今数字化时代&#xff0c;手机号码已成为人们日常生活中不可或缺的一部分。然而&#xff0c;由于各种原因&#xff0c;姓名和手机号码往往并非完全匹配。为了解决这一问题&#xff0c;运营商二要素API应运而生&#xff0c;它能够验证姓名和手机号码是否一致&#xff…

《Vue.js设计与实现》—Vue3响应系统的原理

一、响应式数据与副作用函数 1. 副作用函数 1-1 指令材料 在JavaScript中&#xff0c;副作用函数是指在执行过程中对外部环境产生可观察的变化或影响的函数。这种函数通常会修改全局变量、修改传入的参数、执行I/O操作&#xff08;如读写文件或发送网络请求&#xff09;、修…

四十三、Redis基础

目录 一、认识NoSql 1、定义&#xff1a; 2、常见语法 3、与关系型数据库&#xff08;SQL&#xff09;的区别&#xff1a; 二、认识Redis 1、定义&#xff1a; 2、特征&#xff1a; 3、Key的结构&#xff1a; 三、安装Redis 四、Redis常见命令 1、数据结构介绍 2、…

Hive HWI 配置

前言 1、下载安装好hive后&#xff0c;发现hive有hwi界面功能&#xff0c;研究下是否可以运行&#xff0c;于是使用hive –service hwi命令启动hwi界面报错。 启动hwi功能 2、访问192.168.126.110:9999/hwi&#xff0c;发现访问错误 一、HWI介绍 HWI&#xff08;Hive Web Int…

gRPC .net学习

学习helloworld server用.net client有.net的控制台 和 unity server端 直接使用vs2022创建(需自行看有无装asp.net哦),搜索gPRC,使用6.0吧&#xff0c;创建工程后直接F5跑起来,服务端到此完成 .net控制台client,创建新的控制台,使用NuGet,然后导入server端的Protos文件夹 学…

[C++] STL_priority_queue(优先级队列) 的使用及底层的模拟实现,容器适配器,deque的原理介绍

文章目录 1、priority_queue1.1 priority_queue的介绍和使用1.2 priority_queue的使用模拟实现&#xff1a; 2、容器适配器2.1 什么是适配器2.2 STL标准库中stack和queue的底层结构 3、deque3.1 deque的原理介绍3.2 deque的缺陷 4、为什么选择deque作为stack和queue的底层默认容…

11月客户文章盘点——累计IF 150.5

凌恩生物以打造国内一流生物公司为目标&#xff0c;在科研测序领域深耕不辍&#xff0c;吸纳多名在生物信息高级技术人员的加盟&#xff0c;参与并完成多个高科技项目。现已在宏组学、基因组、表观遗传以及蛋白代谢等多组学及联合分析领域积累了深厚经验&#xff0c;打造出成熟…

Qt图形设计

#include "mywidget.h"MyWidget::MyWidget(QWidget *parent): QWidget(parent) {//窗口相关设置//设置窗口标题this->setWindowTitle("王者荣耀");//设置窗口图标this->setWindowIcon(QIcon("C:\\Users\\28033\\Pictures\\Saved Pictures\\pict…

STM32超声波——HC_SR04

文章目录 一.超声波图片二.时序图三.超声波流程四.单位换算五.取余计算六.换算距离七.超声波代码 一.超声波图片 测量距离&#xff1a;2cm——400cm 二.时序图 (1).以下时序图要先提供一个至少10us的脉冲触发信号&#xff0c;告诉单片机我准备好了&#xff0c;然后该超声波…

最简单的pixel刷机和安装面具、lsposed

一 下载手机对应的系统 1&#xff0c;手机usb连接然后重启进入Fastboot模式&#xff1a;adb reboot bootloader2&#xff0c;找到你下载的系统&#xff0c;Windows 系统 直接运行 flash-all.bat上图 &#xff1a;左边就是安卓11和12的系统&#xff0c;右边是对应的手机型号 下…

思科最新版Cisco Packet Tracer 8.2.1安装

思科最新版Cisco Packet Tracer 8.2.1安装 一. 注册并登录CISCO账号二. 下载 Cisco Packet Tracer 8.2.1三. 安装四. 汉化五. cisco packet tracer教学文档六. 正常使用图 前言 这是我在这个网站整理的笔记,有错误的地方请指出&#xff0c;关注我&#xff0c;接下来还会持续更新…

【LeetCode:1631. 最小体力消耗路径 | BFS + 二分】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

西南科技大学数字电子技术实验三(MSI逻辑器件设计组合逻辑电路及FPGA的实现)FPGA部分

一、实验目的 进一步掌握MIS(中规模集成电路)设计方法。通过用MIS译码器、数据选择器实现电路功能,熟悉它们的应用。进一步学习如何记录实验中遇到的问题及解决方法。二、实验原理 1、4位奇偶校验器 Y=S7i=0DiMi D0=D3=D5=D6=D D1=D2=D4=D7= `D 2、组合逻辑电路 F=A`B C …

ssm基于面向对象的学生事务处理系统分析与设计论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本学生事务处理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…

python+gdal地理坐标转投影坐标

1 前言 地理坐标系&#xff0c;是使用三维球面来定义地球表面位置&#xff0c;以实现通过经纬度对地球表面点位引用的坐标系。 地理坐标系经过地图投影操作后就变成了投影坐标系。而地图投影是按照一定的数学法则将地球椭球面上点的经维度坐标转换到平面上的直角坐标。 2 流程…

RabbitMQ学习二

RabbitMQ学习二 发送者的可靠性生产者连接重试机制生产者确认机制开启生产者确认定义ReturnCallback定义confirmCallback MQ的可靠性交换机和队列持久化消息持久化LazyQueue控制台配置Lazy模式代码配置Lazy模式 消费者的可靠性失败重试机制失败处理策略业务幂等性唯一消息ID业务…

Hiera实战:使用Hiera实现图像分类任务(二)

文章目录 训练部分导入项目使用的库设置随机因子设置全局参数图像预处理与增强读取数据设置Loss设置模型设置优化器和学习率调整策略设置混合精度&#xff0c;DP多卡&#xff0c;EMA定义训练和验证函数训练函数验证函数调用训练和验证方法 运行以及结果查看测试完整的代码 在上…

龙良曲PyTorch入门到实战 深度学习

文章目录 笔记激活函数与Loss的梯度lesson5 手写数字识别问题lesson6 基本数据类型lesson7 创建tensorlesson8 索引和切片lesson9 维度变换lesson10 broadcastinglesson11 分割和合并lesson12 数学运算lesson13 Tensor统计lesson14 Tensor高阶lesson16 什么是梯度lesson17 常见…

初识Ceph --组件、存储类型、存储原理

目录 ceph组件存储类型块存储文件存储对象存储 存储过程 ceph Ceph&#xff08;分布式存储系统&#xff09;是一个开源的分布式存储系统&#xff0c;设计用于提供高性能、高可靠性和可扩展性的存储服务&#xff0c;可以避免单点故障&#xff0c;支持块存储、对象存储以及文件系…

Java项目-瑞吉外卖Day2

完善登录功能&#xff1a; 完善未登录不能访问/backend/index.html。使用拦截器或过滤器。 创建过滤器。 重写doFilter方法。 查看是否过滤成功。 处理流程如下&#xff1a; 添加员工功能&#xff1a; 点击保存&#xff0c;可以看到请求信息。 再看前端代码&a…
最新文章