leetcode(滑动窗口)483.找到字符中所有字母异位词(C++详细解释)DAY4

文章目录

  • 1.题目
    • 示例
    • 提示
  • 2.解答思路
  • 3.实现代码
    • 结果
  • 4.总结

1.题目

给定两个字符串 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 仅包含小写字母

2.解答思路

对于滑动窗口的题,关键就是定义两个left,right用来控制子串的头尾。
还需要明确增大窗口的条件,以及缩小窗口的条件。

定义一个vector对象,用来存储答案(答案就是每一次的left值)。
定义两个无序哈希表分别存储s和p中字符出现的次数。
其中pCount的次数是不变的,用来比较的标准。
其中sCount的次数是随着逐渐的遍历用来控制增大缩小窗口的关键判断条件。
当sCount中字符对应次数大于pCount中次数时,就需要缩小窗口。

3.实现代码

class Solution
{
public:vector<int> findAnagrams(string s, string p){vector<int> answer ;unordered_map<char, int> pCount, sCount; // 无序哈希表int pLen = p.size();int sLen = s.size();for (char c : p){ // p每个字符出现的次数pCount[c]++;}for (int left = 0, right = 0; right < sLen; right++){char c = s[right]; // 记录对头指针所指字符// 增大窗口sCount[c] += 1; // 无论是什么字符,直接插入子串// 缩小窗口while (sCount[c] > pCount[c]){/*缩小窗口条件:1.当下字符不在p中。2.当下字符出现重复(p中没有重复字符)3.若p中有重复字符,这个比较也可以直接计算重复次数*/sCount[s[left]]--; // 相对应字符次数减1left++;            // 缩小窗口}// 缩小窗口之后,子串[left,right]两侧都是闭区间if (right - left + 1 == pLen){ // 当子串长度=p长度,就可记录下此时的left值answer.push_back(left);}}return answer;}
};

结果

在这里插入图片描述

4.总结

这道题不简单,写了好久。最开始没有考虑到p中有重复字符的情况,导致饶了很大圈子。
最后还是参考别人的代码思路仿写的。学习了很好的思路。有收获!

当两个序列的元素都需要计数的时候,可以使用两个哈希表,并且int型的值,都会初始化为0.,直接使用++运算也是ok的。

自信,坚持,upup~

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

通俗易懂:快速排序算法全解析

快速排序&#xff08;Quick Sort&#xff09;是一种高效的分治排序算法&#xff0c;它以其出色的性能和广泛的应用而闻名。本文将深入讲解快速排序的原理、步骤和时间复杂度&#xff0c;并探讨其优势和应用场景。 快速排序原理 快速排序的核心思想是通过选择一个基准元素&…

springboot167基于springboot的医院后台管理系统的设计与实现

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **项…

Bee+SpringBoot稳定的Sharding、Mongodb ORM功能(同步 Maven)

Hibernate/MyBatis plus Sharding JDBC Jpa Spring data GraphQL App ORM (Android, 鸿蒙) Bee 小巧玲珑&#xff01;仅 860K, 还不到 1M, 但却是功能强大&#xff01; V2.2 (2024春节・LTS 版) 1.Javabean 实体支持继承 (配置 bee.osql.openEntityCanExtendtrue) 2. 增强批…

Vue源码系列讲解——虚拟DOM篇【三】(更新子节点)

1. 前言 在上一篇文章中&#xff0c;我们了解了Vue中的patch过程&#xff0c;即DOM-Diff算法。并且知道了在patch过程中基本会干三件事&#xff0c;分别是&#xff1a;创建节点&#xff0c;删除节点和更新节点。创建节点和删除节点都比较简单&#xff0c;而更新节点因为要处理…

“掌握温度,感知湿度,一触即知!”DHT11温湿度传感器,为您的生活增添一份关怀与精准。#非标协议【下】

“掌握温度&#xff0c;感知湿度&#xff0c;一触即知&#xff01;”DHT11温湿度传感器&#xff0c;为您的生活增添一份关怀与精准。#非标协议【下】 前言预备知识1.DHT11温湿度传感器初识1.1产品概述1.2与51单片机接线1.3数据传送逻辑和数据格式 2.发送时序检测DHT11温湿度传感…

npm 上传一个自己的应用(3) 在项目中导入及使用自己上传到NPM的工具

上文 npm 上传一个自己的应用(2) 创建一个JavaScript函数 并发布到NPM 我们创建了一个函数 并发上了npm 最后 我们这里 我们可以看到它的安装指令 这里 我们可以打开一个vue项目 终端输入 我们的安装指令 npm i 自己的包 如下代码 npm i grtest我们在 node_modules目录 下…

[C#]winform制作仪表盘好用的表盘控件和使用方法

【仪表盘一般创建流程】 在C#中制作仪表盘文案&#xff08;通常指仪表盘上的文本、数字或指标显示&#xff09;涉及到使用图形用户界面&#xff08;GUI&#xff09;组件&#xff0c;比如Windows Forms、WPF (Windows Presentation Foundation) 或 ASP.NET 等。以下是一个使用W…

Linux网络通信——TCP/OSI七层模型/TCP/IP(五层或四层模型)/HTTP报文传输原理

文章目录 消息的传输什么是OSI七层模型OSI七层模型的内容物理层&#xff08;Physical Layer&#xff09;&#xff1a;数据链路层&#xff08;Data Link Layer&#xff09;&#xff1a;网络层&#xff08;Network Layer&#xff09;&#xff1a;传输层&#xff08;Transport Lay…

vue3-内置组件-Teleport

Teleport <Teleport> 是一个内置组件&#xff0c;它可以将一个组件内部的一部分模板“传送”到该组件的 DOM 结构外层的位置去。 基本用法 有时我们可能会遇到这样的场景&#xff1a;一个组件模板的一部分在逻辑上从属于该组件&#xff0c;但从整个应用视图的角度来看…

实现注册登录时数据的加密传输(含前后端具体代码)

前言 http/https协议提交在被抓包时请求内容是明文的, 直接传输账号密码的风险非常大&#xff0c;故这里我们要对数据加密处理&#xff0c;并生成校验码&#xff0c;防止数据篡改 目录 ​编辑 前言 具体思路 代码实现 前端信息加密处理&#xff08;Vue&#xff09; 安装…

Java多线程:线程安全

&#x1f451;专栏内容&#xff1a;Java⛪个人主页&#xff1a;子夜的星的主页&#x1f495;座右铭&#xff1a;前路未远&#xff0c;步履不停 目录 一、线程状态1、New&#xff08;初始状态&#xff09;2、Terminated&#xff08;终止状态&#xff09;3、Runnable&#xff08;…

C++类型转化cast from pointer to smaller type ‘int‘ loses information

代码如下 #include <iostream>int main() {int a 10;std::cout << (int)&a << std::endl;return 0; }编译 这段代码是要将地址转化成整数类型&#xff0c;但是在编译时编译器告诉我们这是错的&#xff0c;因为在C中&#xff0c;将指针转换为int类型的…

Spring基础 - Spring核心之面向切面编程(AOP)

Spring基础 - Spring核心之面向切面编程(AOP) 引入 Spring 框架通过定义切面, 通过拦截切点实现了不同业务模块的解耦&#xff0c;这个就叫面向切面编程 - Aspect Oriented Programming (AOP)那么Spring框架又是如何实现AOP的呢&#xff1f; 这就引入代理技术&#xff0c;分静…

Sqlite3安装步骤

1、Sqlite3以下载文件&#xff0c;配置环境变量的方式进行安装。 2、下方链接为官方的下载地址。 sqlite下载地址 2.1、需要两个下载文件&#xff0c;解压后将他们放在一起&#xff0c;假设解压后的路径为E:\sqlite。 sqlite-dll-win-x64-3450100.zip sqlite-tools-win-x6…

C++自定义函数详解

个人主页&#xff1a;PingdiGuo_guo 收录专栏&#xff1a;C干货专栏 铁汁们新年好呀&#xff0c;今天我们来了解自定义函数。 文章目录 1.数学中的函数 2.什么是自定义函数 3.自定义函数如何使用&#xff1f; 4.值传递和引用传递&#xff08;形参和实参区分&#xff09; …

OLED调试简介

文章目录 一、介绍调试方法介绍OLED简介硬件电路OLED驱动函数 二、操作连接线路使用驱动函数显示内容 OLED.c的内容 一、介绍 调试方法介绍 OLED简介 硬件电路 OLED驱动函数 二、操作 连接线路 因为这两个引脚不做配置是浮空状态&#xff0c;在这里直接用电源给OLED供电 使…

嵌入式学习之Linux入门篇笔记——10,Linux连接档概念

配套视频学习链接&#xff1a;http://【【北京迅为】嵌入式学习之Linux入门篇】 https://www.bilibili.com/video/BV1M7411m7wT/?p4&share_sourcecopy_web&vd_sourcea0ef2c4953d33a9260910aaea45eaec8 目录 1.Linux 下的连接档种类 2.什么是 inode&#xff1f; 3.什…

Node.js JSON Schema Ajv依赖库逐步介绍验证类型和中文错误提示

在构建应用程序时&#xff0c;数据的有效性是至关重要的。为了确保传入的数据符合预期的格式和规范&#xff0c;我们可以使用 Ajv&#xff08;Another JSON Schema Validator&#xff09;进行验证。在这篇博文中&#xff0c;我们将从头开始学习 Ajv&#xff0c;逐步介绍验证类型…

Linux探秘之旅:透彻理解路径、命令与系统概念

目录 如何远程连接 远程登录简明指南 linux区别 1.严格区分大小写 2.linux的命令返回结果判断 3.如何查看网络信息 4.关于后缀名&#xff08;Linux不关心文件后缀&#xff09; 4.1 需要记忆的后缀 5.echo命令 6.linux一切皆文件 6.1比如磁盘的文件 6.2可执行文件 …

在面试中如何回复擅长vue还是react

当面试官问及这个问题的时候&#xff0c;我们需要思考面试官是否是在乎你是掌握vue还是react吗&#xff1f;&#xff1f;&#xff1f; 在大前端的一个环境下&#xff0c;当前又有AI人工智能的加持辅助&#xff0c;我们是不是要去思考企业在进行前端岗位人员需求的时候&#xf…