模块二——滑动窗口:438.找到字符串中所有字母异位词

文章目录

  • 题目描述
  • 算法原理
    • 滑动窗口+哈希表
  • 代码实现

题目描述

题目链接:438.找到字符串中所有字母异位词
在这里插入图片描述

算法原理

滑动窗口+哈希表

  • 因为字符串p的异位词的⻓度⼀定与字符串p 的⻓度相同,所以我们可以在字符串s 中构造⼀个⻓度为与字符串p的⻓度相同的滑动窗⼝,并在滑动中维护窗⼝中每种字⺟的数量;
  • 当窗⼝中每种字⺟的数量与字符串p 中每种字⺟的数量相同时,则说明当前窗⼝为字符串p的异位词;
  • 因此可以⽤两个⼤⼩为26 的数组来模拟哈希表,⼀个来保存s 中的⼦串每个字符出现的个数,另⼀个来保存p中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。

代码实现

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = { 0 };//统计字符串p中每个字符出现的个数
        for(auto ch : p)hash1[ch - 'a']++;
        int hash2[26] = { 0 };//统计窗口里面每一个字符出现的个数
        vector<int> res;

        for(int left = 0,right = 0,count = 0;right < s.size();right++)//1.控制窗口
        {
            char in = s[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a'])count++;//2.进窗口+维护count
            while(right - left + 1 > p.size())//3.判断
            {
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a'])count--;//维护count+出窗口
            }
            if(count == p.size()) res.push_back(left);//更新结果
        }
        return res;
    }
};

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

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

相关文章

基础算法(2):排序(2):计数排序

1.计数排序实现 计数排序是一个非基于比较的稳定的线性时间的排序算法&#xff0c;而选择排序是基于比较的&#xff0c;计数排序不用&#xff0c;它的实现依靠计数。 工作原理&#xff1a;使用一个额外的数组&#xff0c;其中第i个位置是待排序数组1中值等于i的元素的个数&…

Ansible介绍与安装

Ansible目前是运维自动化工具中最简单、容易上手的一款优秀软件&#xff0c;能够用来管理各种资源。用户可以使用Ansible自动部署应用程序&#xff0c;以此实现IT基础架构的全面部署。例如&#xff0c;借助于Ansible&#xff0c;我们可以轻松地对服务器进行初始化配置、安全基线…

显示器件是什么

显示器件 电子元器件百科 文章目录 显示器件前言一、显示器件是什么二、显示器件的类别三、显示器件的应用实例四、显示器件的作用原理总结前言 显示器件根据不同的技术原理和应用领域,具有不同的特点和优势,可适用于电子产品、电视、计算机显示器、手持设备、汽车仪表盘等…

产品入门第四讲:Axure动态面板

&#x1f4da;&#x1f4da; &#x1f3c5;我是默&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; ​​​​​ &#x1f31f;在这里&#xff0c;我要推荐给大家我的专栏《Axure》。&#x1f3af;&#x1f3af; &#x1f680;无论你是编程小白&#xff0c;还…

Java刷题篇——合并两个有序数组

1.题目描述 给出一个有序的整数数组A 和有序的整数数组 B&#xff0c;请将数组B合并到数组A中&#xff0c;变成一个有序的升序数组。 数据范围&#xff1a;0 < n,m < 100, |A~i~| < 100, |B~i~| < 100 注意&#xff1a; 保证 A 数组有足够的空间存放 B 数组的元…

(C++)只出现一次的数字I--异或

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能&#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://le…

AI:100-基于卷积神经网络的农作物生长状态监测

🚀 本文选自专栏:人工智能领域200例教程专栏 从基础到实践,深入学习。无论你是初学者还是经验丰富的老手,对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带有在本地跑过的核心代码,详细讲解供大家学习,希望可以帮到大家。欢迎订阅支持,正在不断更新…

Axure的动态面板

目录 动态面板 什么是Auxre动态模板 动态模板的步骤 应用场景 实战案例 轮播图 多功能登录界面 主界面左侧菜单栏 动态面板 什么是Auxre动态模板 动态面板是Axure中的一个重要功能&#xff0c;它允许用户创建可交互的页面&#xff0c;并模拟用户与页面的交互。通过添加元素…

智能指针管理“newed对象”

为什么要有智能指针&#xff1f; 指针智能是管理管理动态内存分配对象的一种机制。它提供了自动管理内存&#xff0c;避免常见内存泄漏和悬空指针。 对于上述Func函数的操作&#xff0c;一不小心就会产生很多问题。 p1 new时候抛异常 什么都不做p2 new时候抛异常 p1需要被清理…

Apache DolphinScheduler 社区荣获 “2023 年度优秀开源技术团队“ 奖项

在开源社区日益繁荣的今天&#xff0c;我们非常荣幸地宣布&#xff1a;Apache DolphinScheduler 社区在 OSCHINA 平台的评选中荣获了“2023 年度优秀开源技术团队”奖项。这一奖项反映了我们社区在过去一年里在内容发表的深度与广度、活动运营影响力以及对开源文化的推广方面所…

每日一题 --- 2477. 到达首都的最少油耗

链式前向星解法 核心点是我dfs两次&#xff0c;第一次是求出每个节点的叶子节点有多少个&#xff1f; 因为我们可以看做从当前节点出发到当前节点的根节点的话&#xff0c;那么需要知道当前节点叶子节点个数&#xff0c;也就是我们让当前节点的叶子结点&#xff08;代表&…

yolov8常用命令

1.运行预测 &#xff08;1&#xff09;运行目标检测模型&#xff1a; yolo predict modelyolov8n.pt sourcebus.jpg &#xff08;2&#xff09;运行目标检测与分割模型 yolo predict modelyolov8n-seg.pt sourcebus.jpg 2.模型训练 复制coco128.yaml更名为myDetect.y…

检测车牌的SIFT特征并匹配

# 代码5-14 检测车牌的SIFT特征并匹配 import cv2img1 cv2.imread(../data/plate.jpg) img2 cv2.imread(../data/car.jpg)sift cv2.SIFT_create() # 利用sift.detectAndCompute()函数找到特征点&#xff0c;计算描述符&#xff1b; kp1, des1 sift.detectAndCompute(img1, …

Unity Sentis首份教程来啦,利用AI模型创建先进功能

Unity 推出的 Sentis&#xff0c;赋予开发者将 AI 模型导入游戏和应用程序中的能力。现在&#xff0c;Sentis 已进入预发布的开放测试阶段&#xff0c;用户可以在所有类型的项目中实现物体识别、语音识别和智能 NPC 等复杂功能。 这些 AI 模型一旦通过 ONNX 文件标准导入&…

地图自定义省市区合并展示数据整合

需求一&#xff1a;将省级地图下的两个市合并成一个区域&#xff0c;中间的分割线隐藏。 1、访问下方地址&#xff0c;搜索并下载省级地图json文件。 地址&#xff1a;https://datav.aliyun.com/portal/school/atlas/area_selector 2、切换到边界生成器&#xff0c;上传刚刚下…

基于Java+SpringBoot+Vue3+Uniapp前后端分离考试学习一体机设计与实现企业级2.01版本(视频讲解,已发布上线)

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…

【经验分享】gemini-pro和gemini-pro-vision使用体验

Gemini Gemini已经对开发者开放了Gemini Pro的使用权限&#xff0c;目前对大家都是免费的&#xff0c;每分钟限制60条&#xff0c;至少这比起CloseAI的每个账户5刀限速1min3条要香的多&#xff0c;目前已于第一时间进行了体验 一句话总结&#xff0c;google很大方&#xff0c;但…

web服务器之——搭建两个基于域名访问的网站

目录 要求&#xff1a; 一、准备工作&#xff1a;web服务器搭建 第一步&#xff1a;挂载 第二步&#xff1a;编辑配置文件 第三步&#xff1a;安装软件包 第四步&#xff1a;启动httpd 查看配置文件&#xff1a; 第五步&#xff1a;设置防火墙状态&#xff1a; 重启服务…

虹科技术 | IO-Link Wireless如何赋能工厂车间迈向无线自动化?

大规模定制、卓越运营和商业智能正在从根本上改变制造业&#xff0c;为了在竞争中立于不败之地&#xff0c;制造商需要更加灵活、通用、可扩展和具有成本效益的机器和生产线。随着制造商向工业 4.0 迈进&#xff0c;更好的适应性、更高的吞吐量和更短的停机时间是他们的共同要求…

【C++】策略模式

目录 一、简介1. 含义2. 特点 二、实现1. 策略接口&#xff08;Strategy Interface&#xff09;2. 具体策略类&#xff08;Concrete Strategies&#xff09;3. 上下文类&#xff08;Context&#xff09;4. 使用策略模式 三、总结如果这篇文章对你有所帮助&#xff0c;渴望获得你…