力扣438. 找到字符串中所有字母异位词

Problem: 438. 找到字符串中所有字母异位词

文章目录

  • 题目描述
  • 思路及解法
  • 复杂度
  • Code

题目描述

在这里插入图片描述
在这里插入图片描述

思路及解法

1.编写辅助函数bool same(vector& need, vector& matched)

1.1 以need为标准,循环对比need和matched的每一个位置的元素值是否相等

2.获取s和p的长度,lenS和lenP;
3.创建vector needs(26,0);,将p中的字符映射到其中needs[p[i] - ‘a’]++;
4.创建窗口:创建vector matched(26,0);,并定义指针starP、endP,并且将字符串s中的前lenP个字符映射到matched中,并调用same进行一次判断,若满足则将startP添加到结果集合result中
5.维护窗口:当两个指针均小于lenS时执行**matched[s[starP] - ‘a’]–;matched[s[endP] - ‘a’]++;**并且让startP与endP自增,并调用same函数,将字母异位置词的起始位置添加到result中

复杂度

时间复杂度:

O ( 1 ) O(1) O(1)

空间复杂度:

O ( 1 ) O(1) O(1)

Code

class Solution {
public:
    /**
     * Sliding window
     *
     * @param s The string given to be matched
     * @param p Substring
     * @return vector<int>
     */
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.length();
        int pLen = p.length();
        if (pLen > sLen) {
            return {};
        }
        vector<int> needs(26,0);
        for (int i = 0; i < pLen; ++i) {
            needs[p[i] - 'a']++;
        }
        vector<int> matched(26,0);
        int starP = 0;
        int endP = 0;
        vector<int> result;
        while (endP < pLen) {
            matched[s[endP] - 'a']++;
            endP++;
        }
        if (same(needs, matched)) {
            result.push_back(starP);
        }
        while (starP < sLen && endP < sLen) {
            matched[s[starP] - 'a']--;
            matched[s[endP] - 'a']++;
            starP++;
            endP++;
            if (same(needs, matched)) {
                result.push_back(starP);
            }
        }
        return result;
    }
private:
    /**
     *Determines whether the values in two arrays (within a given range) are equal
     * 
     * @param need Judgment reference array
     * @param matched Array to match each time
     * @return bool
     */
    bool same(vector<int>& need, vector<int>& matched) {
        for (int i = 0; i < need.size(); ++i) {
            if (need[i] != matched[i]) {
                return false;
            }
        }
        return true;
    }
};

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

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

相关文章

NAT---网络地址转换技术

Network Address Translation 1、起源&#xff1a;ip地址不够用 2、作用&#xff1a;让私网地址映射成公网地址&#xff0c;进而访问网络。 3、私网Ip地址的范围&#xff1a; A类&#xff1a;10.0.0.0-10.255.255.255 B类&#xff1a;172.16.0.0-172.31.255.255 C类&…

多线程合并练习题,线程安全(售票任务引入)--学习JavaEE的day30

day30 练习&#xff08;day29&#xff09; 注意代码注释&#xff0c;里面涉及代码实现遇到问题及解决方案&#xff0c;由于理解方便没有单独出来 1.计算任务 1.计算任务&#xff0c;一个包含了2万个整数的数组&#xff0c;分拆了多个线程来进行并行计算&#xff0c;最后汇总出…

Open CASCADE 用户指南:可视化

文章目录 介绍基本概念呈现(Presentation)Presentation 的结构Presentation 包(package)基本示例&#xff1a;如何显示 3D 对象 选择(Selection)术语和概念算法包和类(Packages and classes)使用示例 应用交互服务&#xff08;AIS&#xff09;介绍交互对象呈现(Presentations)隐…

【C语言】【Leetcode】88. 合并两个有序数组

文章目录 一、题目二、思路再思考 一、题目 链接: link 二、思路 这题属于简单题&#xff0c;比较粗暴的做法就是直接比较两个数组&#xff0c;先把第二个数组加到第一个的后面&#xff0c;如何冒泡排序&#xff0c;这种方法简单粗暴但有效&#xff0c;可是不适用于这题&…

Vue3使用v-if指令进行条件渲染

Vue3使用v-if指令进行条件渲染 条件渲染是根据条件的真假来有条件地渲染元素。在Vue.js 3.x中&#xff0c;常见的条件渲染包括使用v-if指令和v-show指令。本文讲解使用v-if指令进行条件渲染。 2.3.1 v-if/v-else-if/v-else 在Vue中使用v-if、v-else-if和v-else指令实现条件…

数据结构·二叉树(1)

目录 1 树的概念及结构 1.1 树的结构 1.2 树的概念 1.3树的表示 2 二叉树的概念及结构 2.1二叉树的概念 2.2 特殊的二叉树 2.3 二叉树的存储结构 1 树的概念及结构 1.1 树的结构 前面所学到的顺序表链表等&#xff0c;都是线性的数据结构&#xff0c;今天介绍的树&am…

第九届蓝桥杯大赛个人赛省赛(软件类)真题C 语言 A 组-第几个幸运数字

幸运数字是可以被3,5,7任一整除的数字&#xff0c;列举小明号码内的所有可能组合并计数。注意别忘了把1占的一位减去。 #include<stdio.h> typedef long long ll; int main(){long long ans 0, n 59084709587505LL;for(ll i 1; i < n; i * 3){//计算小于等于n的数…

代码随想录训练营Day32:● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

122.买卖股票的最佳时机II 题目链接 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/ 题目描述 思路 看完视频讲解之后豁然开朗啊简直了&#xff01;&#xff01;&#xff01; 统计后一天减去前一天&#xff0c;差值为正数的&#xff0c;再…

一篇文章带你搞定接单的多种渠道,赶紧码住!!!

相信大家也看到了不少人通过网络接单实现年入30W&#xff0c;彻底财富自由&#xff01;咱看了&#xff0c;真的很难不心痒痒&#xff0c;想加入其中&#xff0c;大干一场&#xff01;毕竟搞钱嘛&#xff01;才是王道。但是呢&#xff0c;也有很多人心向往之&#xff0c;奈何不知…

C++剑指offer与高频面试题源码解答与分析

这是博主在当初秋招刷题时候记录的剑指offer第二版以及一些高频题的C源码和解法分析&#xff0c;可以说把这上面的题练好了面试不虚&#xff0c;最后也顺利帮助我拿下baidu ali meituan等多家大厂offer。整篇文章写了大概5W个字&#xff0c;也是积累了很长一段时间的作品&#…

MYSQL通过substr函数与instr函数截取字符串

mysql通过substr函数与instr函数截取字符串 1.从字段左边开始第三位&#xff0c;截取到结束2.截取字段前三位3.截取字段后三位4.从字段右边开始第三位&#xff0c;往后截取一位5.从字段小数点的位置开始&#xff0c;向后截取两位&#xff08;使用了instr&#xff08;&#xff0…

leetcode刷题日记-外观数组

题目描述 解题思路 初始化字符串 init 为 “1”&#xff0c;作为外观数列的第一项。 通过循环迭代生成外观数列的下一项&#xff0c;循环次数为 n-1&#xff0c;因为已经初始化了第一项。 在每次迭代中&#xff0c;通过两个指针 pos 和 start 来遍历当前项 init&#xff0c;po…

22.保护性暂停扩展(一对一)

如果需要多个类之间使用GuardedObject对象&#xff0c;作为参数传递不是很方便&#xff0c;因此设计一个解耦的中间类&#xff0c;这样不仅能够解耦结果的等待者和结果生产者&#xff0c;还能够支持多个任务的管理。 Futures就好比居民楼一层的信箱&#xff0c;每个信箱有房间的…

大数据面试题 —— Flume

目录 介绍 FlumeFlume 架构请说一下你提到的几种 source 的不同点Flume 传输数据时如何保证数据一致性TailDir 为什么可以断点重传说下Flume事务机制Sink 消费能力弱&#xff0c;Channel 会不会丢失数据数千个Flume要怎么统一配置&#xff0c;修改就分发吗Flume一个节点宕机了怎…

【科研基础】分布式信源编码与中继通信

[1] Bian, Chenghong, et al. “Deep joint source-channel coding over cooperative relay networks.” arXiv preprint arXiv:2211.06705 (2022). [2] Bian, Chenghong, et al. “Process-and-Forward: Deep Joint Source-Channel Coding Over Cooperative Relay Networks.”…

还在用传统知识库?AI知识库才是企业的最优选择

在数字化和信息化日趋严重的时代&#xff0c;企业不仅要处理海量的数据&#xff0c;同时还要有效地管理和利用它们。这就使得知识库&#xff0c;作为一种集中存储、管理和共享知识资源的工具&#xff0c;被越来越多的企业所重视。然而&#xff0c;随着技术的快速迭代&#xff0…

RabbitMQ 安装保姆级教程

目录 1.MQ引言 1.1 什么是MQ 1.2 MQ有哪些 1.3 不同MQ特点 2.RabbitMQ 的引言 2.1 RabbitMQ 2.2 RabbitMQ 的安装 2.2.1 下载 2.2.2 下载的安装包 2.2.3 安装步骤 3. RabiitMQ 配置 3.1RabbitMQ 管理命令行 3.2 web管理界面介绍 3.2.1 overview概览 3.2.2 Admin用…

蓝桥杯物联网遇见的重大BUG及其产生原因和解决方法

BUG列表 1、ADC的RP2显示一直为0&#xff1a;2、LORX_Tx发送数据乱码&#xff1a;3、strcmp比较char a[2] {1, 2}与“12”字符串是否相等板子会死机&#xff1a;4、LORA_Tx和LORA_Rx放一起会接收不到数据&#xff1a;5、RTC获取到静止时间&#xff1a;6、ADC获取RP1和RP2模拟量…

基于java+springboot+vue实现的图书借阅系统(文末源码+Lw+ppt)23-328

摘 要 伴随着我国社会的发展&#xff0c;人民生活质量日益提高。于是对系统进行规范而严格是十分有必要的&#xff0c;所以许许多多的信息管理系统应运而生。此时单靠人力应对这些事务就显得有些力不从心了。所以本论文将设计一套“期待相遇”图书借阅系统&#xff0c;帮助商…