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]]--; // 相对应字符次数减1
                left++;            // 缩小窗口
            }

            // 缩小窗口之后,子串[left,right]两侧都是闭区间
            if (right - left + 1 == pLen)
            { // 当子串长度=p长度,就可记录下此时的left值
                answer.push_back(left);
            }
        }
        return answer;
    }
};

结果

在这里插入图片描述

4.总结

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

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

自信,坚持,upup~

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

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

相关文章

03-抓包_封包_协议_APP_小程序_PC应用_WEB应用

抓包_封包_协议_APP_小程序_PC应用_WEB应用 一、参考工具二、演示案例&#xff1a;2.1、WEB应用站点操作数据抓包-浏览器审查查看元素网络监听2.2、APP&小程序&PC抓包HTTP/S数据-Charles&Fiddler&Burpsuite2.3、程序进程&网络接口&其他协议抓包-WireSh…

three.js 向量方向(归一化.normalize)

效果&#xff1a; <template><div><el-container><el-main><div class"box-card-left"><div id"threejs" style"border: 1px solid red"></div><div><p><el-button type"primary…

c#: 表达式树的简化

环境&#xff1a; .net 6 一、问题&#xff1f; 有下面的表达式&#xff1a; var nums new List<int> { 1, 2, 3 }; Expression<Func<int, bool>> exp i > i > nums.Max();我们知道&#xff0c;它其实就是&#xff1a;exp i > i > 3; 那么…

史上最全嵌入式(学习路线、应用开发、驱动开发、推荐书籍、软硬件基础)

废话不多说直接上思维导图&#xff01; 如果有觉得图片看不清楚的&#xff0c;有疑问的&#xff0c;可在评论区进行留言&#xff01; 群号&#xff1a; 228447240 嵌入式总括 嵌入式书籍推荐 嵌入式软件知识 嵌入式硬件知识 嵌入式应用开发 嵌入式驱动开发 嵌入式视频推荐: 韦…

5秒搭建PalWorld幻兽帕鲁游戏服务器,你信吗?

5秒搭建PalWorld幻兽帕鲁游戏服务器&#xff0c;你信吗&#xff1f;腾讯云推出幻兽帕鲁专属镜像系统&#xff0c;直接选择镜像&#xff0c;5秒搞定&#xff0c;全自动化部署。 幻兽帕鲁太火了&#xff0c;官方palworld服务器不稳定&#xff1f;不如自建服务器&#xff0c;基于…

双归同一运营商的 BGP 部署

一、拓朴如下&#xff1a; 要求&#xff1a; 1、AS100 只接收 AS200 和 300 的路由&#xff0c;不接收其它 AS 的明细路由&#xff1b; 2、对于 AS100 的业务流量出方向&#xff0c;所有到 AS200 和 300 的流量&#xff0c;优先选择 Line-1&#xff0c;而到 AS400 的流…

SpringBoot Security安全认证框架初始化流程认证流程之源码分析

SpringBoot Security安全认证框架初始化流程&认证流程之源码分析 以RuoYi-Vue前后端分离版本为例分析SpringBoot Security安全认证框架初始化流程&认证流程的源码分析 目录 SpringBoot Security安全认证框架初始化流程&认证流程之源码分析一、SpringBoot Security安…

5.electron之主进程起一个本地服务

如果可以实现记得点赞分享&#xff0c;谢谢老铁&#xff5e; Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 Electron 将 Chromium 和 Node.js 嵌入到了一个二进制文件中&#xff0c;因此它允许你仅需一个代码仓库&#xff0c;就可以撰写支持 Windows、…

基于SpringBoot和PostGIS的震中影响范围可视化实践

目录 前言 一、基础数据 1、地震基础信息 2、全国行政村 二、Java后台服务设计 1、实体类设计 2、Mapper类设计 3、控制器设计 三、前端展示 1、初始化图例 2、震中位置及影响范围标记 3、行政村点查询及标记 总结 前言 地震等自然灾害目前还是依然不能进行准确的预…

基于Springboot的足球社区管理系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的足球社区管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构…

8.0 Zookeeper 四字命令教程详解

zookeeper 支持某些特定的四字命令与其交互&#xff0c;用户获取 zookeeper 服务的当前状态及相关信息&#xff0c;用户在客户端可以通过 telenet 或者 nc&#xff08;netcat&#xff09; 向 zookeeper 提交相应的命令。 安装 nc 命令&#xff1a; $ yum install nc …

[office] Excel 2016怎么绘图?Excel2016绘图图文教程 #媒体#经验分享

Excel 2016怎么绘图&#xff1f;Excel2016绘图图文教程 这篇文章主要为大家介绍了Excel 2016怎么绘图&#xff1f;这篇文章主要介绍了Excel2016绘图图文教程 Excel作为数据处理分析软件&#xff0c;是非常好用的软件。里面可以进行数据统计与分析&#xff0c;如果要使得 Exce…

坚持刷题|二叉树的最近公共祖先

文章目录 题目考察点代码实现实现总结为什么不用迭代的方法实现&#xff1f;二叉搜索树的最近公共祖先 Hello&#xff0c;大家好&#xff0c;我是阿月。坚持刷题&#xff0c;老年痴呆追不上我&#xff0c;今天刷&#xff1a;二叉树的最近公共祖先 题目 236.二叉树的最近公共祖…

JavaWeb后端开发(第一期):Maven基础、Maven的安装配置、如何创建maven项目模块、maven的生命周期

Java后端开发&#xff1a;2024年2月6日 -> LiuJinTao 文章目录 JavaWeb后端开发&#xff08;第一期&#xff09; &#xff1a; maven基础一、 maven介绍1.1 什么maven呢&#xff1a;1.2 maven的作用1.3 maven 模型1.4 maven 仓库 二、maven 安装2.1 配置本地仓库2.2 配置阿里…

设计模式-行为型模式(下)

1.访问者模式 访问者模式在实际开发中使用的非常少,因为它比较难以实现并且应用该模式肯能会导致代码的可读性变差,可维护性变差,在没有特别必要的情况下,不建议使用访问者模式. 访问者模式(Visitor Pattern) 的原始定义是&#xff1a; 允许在运行时将一个或多个操作应用于一…

调和平均

L1-4 调和平均 分数 10 作者 陈越 单位 浙江大学 N 个正数的算数平均是这些数的和除以 N&#xff0c;它们的调和平均是它们倒数的算数平均的倒数。本题就请你计算给定的一系列正数的调和平均值。 输入格式&#xff1a…

Java学习-常用API(一)

Object类 Object类及其常用方法&#xff1a; 代码示例&#xff1a; Objects Objects类的引入&#xff0c;定义及其常见的方法&#xff1a; 示例 包装类 什么是包装类&#xff1f; 自动装箱和自动拆箱&#xff1a; 常用方法&#xff1a; 注意&#xff1a;字符串的 数值&#xf…

VS无法使用万能头文件#include <bits/stdc++.h> 的解决办法

第一步在vs中打出可以使用的头文件 如#include<cmath> 点击F12转到文档 上面窗口右键找到打开所在文件夹 创建一个名字为bits的文件夹 里面创建一个text文件 // C includes used for precompiling -*- C -*-// Copyright (C) 2003-2015 Free Software Foundation, In…

Java小区物业管理系统

技术架构&#xff1a; springboot mybatis thymeleaf Mysql5.7 有需要该项目的小伙伴可以私信我你的Q。 功能描述&#xff1a; 控制台、数据库、楼栋管理、单元管理、房屋管理、车位管理、缴费类型、缴费管理、公告管理、维修管理、投诉管理、用户管理 效果图&#xff…

ONLYOFFICE 文档开发者版 8.0:API和文档生成器更新

随着 8.0 版新功能的发布&#xff0c;我们更新了编辑器、文档生成器和插件的 API。请阅读本文了解详情。 PDF 支持 我们在 documentType 参数中添加了 pdf 文档这一类型。现在完全支持PDF文件*&#xff0c;包括含有可填写字段的文件&#xff0c;并且可以在ONLYOFFICE PDF 编辑…