leecode438 | 找到所有字符串中的异位词

题意大致是,给定两个字符串,s 和 p
其中 要在s 中找到由p的元素组成的子字符串,记录子字符串首地址

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m = s.size(), n = p.size();
        if(m < n)return {};

        vector<int> hashTable(26);
        for(auto ch : p){
            hashTable[ch - 'a']++;
        }
        vector<int> ret;

        /*
            手动移动滑动窗口右边界,如果是新元素循环循环移动左边界,直到找到右边的那个元素
            如果串口长度于p的长度一致,达成条件
        */
        for(int l = 0, r = 0; r < m; ++r){
            hashTable[s[r] - 'a']--;
            while(hashTable[s[r] - 'a'] < 0){
                hashTable[s[l] - 'a']++;
                l++;
            }
            if(r - l + 1 == n){
                ret.push_back(l);
            }
        }

        return ret;

    }
};

其实很容易想到滑动窗口

这道题解的思路是,先把p的所有元素记录下来,然后开始遍历滑动串口的右边界,直接hashTable[s[r]]–;
如果其值>= 0 说明遍历的滑动窗口(s的子串)有p 的元素,不管 ,继续移动右窗口,直到滑出边界
如果 < 0 说明 新元素,此时右边界不能动,动左边界,左边界怎么动呢?就是左边界不断加元素,不断右移,最后把新元素添加进去了。
在窗口滑动的过程中,如果满足 r - l + 1 == n 说明找到了一个满足 p 的子字符串。

//还有一个
// 思想是一样的,但是看着会比较啰嗦

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> mp;
        vector<int> result;
        int s_len = s.size(), p_len = p.size();
        for(auto & c : p){
            mp[c]++;
        }
        int left = 0, right = 0, count = p_len;
        // 初始化滑动窗口
        while(right < p_len){
            if(mp.count(s[right]) > 0 && mp[s[right]] > 0){
                count--;
            }
            mp[s[right]]--;
            right++;

        }

        if(count == 0){
            result.push_back(left);
        }

        //移动滑动窗口
        while(right < s_len){
            if(mp.count(s[left]) > 0 && mp[s[left]] >= 0){
                count++;
            }
            mp[s[left]]++;
            left++;
            if(mp.count(s[right]) > 0 && mp[s[right]] > 0){
                count--;
            }
            mp[s[right]]--;
            right++;
            if(count == 0){
                result.push_back(left);
            }
        }
        return result;
    }
};

在这里插入图片描述

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

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

相关文章

python botos s3 aws

https://boto3.amazonaws.com/v1/documentation/api/latest/reference/services/s3.html AWS是亚马逊的云服务&#xff0c;其提供了非常丰富的套件&#xff0c;以及支持多种语言的SDK/API。本文针对其S3云储存服务的Python SDK&#xff08;boto3&#xff09;的使用进行介绍。 …

每日一题——阶乘计算升级版

题目链接&#xff1a; 6-10 阶乘计算升级版 - 基础编程题目集 (pintia.cn) 题目&#xff1a; 6-10 阶乘计算升级版 分数 20 本题要求实现一个打印非负整数阶乘的函数。 函数接口定义&#xff1a; void Print_Factorial ( const int N ); 其中N是用户传入的参数&#xff…

解锁智能未来:用Ollama开启你的本地AI之旅

Ollama是一个用于在本地运行大型语言模型&#xff08;LLM&#xff09;的开源框架。它旨在简化在Docker容器中部署LLM的过程&#xff0c;使得管理和运行这些模型变得更加容易。Ollama提供了类似OpenAI的API接口和聊天界面&#xff0c;可以非常方便地部署最新版本的GPT模型并通过…

商业银行业务与管理

商业银行业务与管理 资产负债表恒等式中国商业银行的资产负债表商业银行的业务种类银行运行管理的案例银行管理的基本准则流动性管理资产和负债管理资本充足管理 资产负债表恒等式 &#xff08;一般&#xff09;资产负债所有者权益 一个公司的资产是由负债和所有者权益所构成…

欧拉回路算法

1 基本概念 1.1 欧拉路径和欧拉回路 欧拉路径&#xff1a;欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径&#xff0c;并且图中每条边通过的且只通过一次。 欧拉回路:欧拉回路是指起点和终点相同的欧拉路。 注意&#xff1a;如果欧拉回路&#xff0c;那么一定存在…

策略模式【行为模式C++】

1.概述 策略模式是一种行为设计模式&#xff0c; 它能让你定义一系列算法&#xff0c; 并将每种算法分别放入独立的类中&#xff0c; 以使算法的对象能够相互替换。 策略模式通常应用于需要多种算法进行操作的场景&#xff0c;如排序、搜索、数据压缩等。在这些情况下&#x…

【C++]C/C++的内存管理

这篇博客将会带着大家解决以下几个问题 1. C/C内存分布 2. C语言中动态内存管理方式 3. C中动态内存管理 4. operator new与operator delete函数 5. new和delete的实现原理 6. 定位new表达式(placement-new) 1. C/C内存分布 我们先来看下面的一段代码和相关问题 int global…

Unity 通过权重做随机

我们可以通过Random.Range方法结合权重来实现随机选择。具体步骤如下&#xff1a; 首先&#xff0c;创建一个数组&#xff0c;其中包含你要选择的项目&#xff0c;并为每个项目分配一个权重值。 计算所有权重值的总和。 使用Random.Range生成一个介于0和总权重之间的随机数。…

Hadoop+Spark大数据技术(微课版)曾国荪、曹洁版思维导图第四次作业 (第4章 HBase分布式DB)

1.简述Hbase的特点及与传统关系数据库的区别 HBase与传统关系数据库的区别 &#xff08;1&#xff09;数据类型 关系数据库具有丰富的数据类型&#xff0c;如字符串型、数值型、日期型、二进制型等。HBase只有字符串数据类型&#xff0c;数据的实际类型都是交由用户自己编写程序…

Google Imagen 2对比OpenAI的Dall-E 3 - 同一提示,不同结果

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

python怎么输出小数

先将整型转换成float型&#xff0c;再进行计算&#xff0c;结果就有小数了。 >>> a 10 >>> b 4 >>> c a/b >>> a,b,c (10, 4, 2) >>> a float(a) >>> d a/b >>> a,b,d (10.0, 4, 2.5) >>> 注意&…

1036: 寻找整数序列的主元素

解法&#xff1a; #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() {int n;cin >> n;vector<int> arr(n);vector<int> tong(1000);for (auto& x : arr) {cin >> x;tong[x];}int pma…

如何在Windows安装LocalSend并结合内网穿透实现公网跨平台远程文件互传

文章目录 1. 在Windows上安装LocalSend2. 安装Cpolar内网穿透3. 公网访问LocalSend4. 固定LocalSend公网地址 本篇文章介绍在Windows中部署开源免费文件传输工具——LocalSend&#xff0c;并且结合cpolar内网穿透实现公网远程下载传输文件。 localsend是一款基于局域网的文件传…

宜搭无权查询该应用信息,唯一排查码:21081d4e17130865292352743e9ed8

这种问题可能是关联表单出现了问题&#xff0c;当前应用中没有这个表单 所以就出现了应用无权访问的问题

备战蓝桥杯(日益更新)(刷题)

备战蓝桥杯&#xff08;日益更新&#xff09;&#xff08;刷题&#xff09; 文章目录 备战蓝桥杯&#xff08;日益更新&#xff09;&#xff08;刷题&#xff09;前言&#xff1a;一、二分&#xff1a;1. acwing503 借教室&#xff1a;&#xff08;二分 差分&#xff09;2. ac…

荔枝派LicheePi 4A RISCV板子支持的好玩的AI模型

荔枝派LicheePi 4A 是基于 Lichee Module 4A 核心板的 高性能 RISC-V Linux 开发板&#xff0c;以 TH1520 为主控核心&#xff08;4xC9101.85G&#xff0c; RV64GCV&#xff0c;4TOPSint8 NPU&#xff0c; 50GFLOP GPU&#xff09;&#xff0c;板载最大 16GB 64bit LPDDR4X&…

JavaScript(七)-高级技巧篇

文章目录 深浅拷贝浅拷贝深拷贝 异常处理thorw抛异常try/catch捕获异常debugger 处理thisthis指向改变this 性能优化防抖lodash实现防抖手写防抖函数 节流 - throttle 深浅拷贝 浅拷贝 深拷贝 深拷贝有三种方式 通过递归实现深拷贝 一定先写数组再写对象 lodash/cloneDeep …

PostgreSQL入门到实战-第二十八弹

PostgreSQL入门到实战 PostgreSQL中数据分组操作(三)官网地址PostgreSQL概述PostgreSQL中GROUPING SETS命令理论PostgreSQL中GROUPING SETS命令实战更新计划 PostgreSQL中数据分组操作(三) 使用PostgreSQL grouping sets子句在查询中生成多个分组集。 官网地址 声明: 由于操…

[尚硅谷flink] 检查点笔记

在Flink中&#xff0c;有一套完整的容错机制来保证故障后的恢复&#xff0c;其中最重要的就是检查点。 文章目录 11.1 检查点11.1.1 检查点的保存1&#xff09;周期性的触发保存2&#xff09;保存的时间点3&#xff09;保存的具体流程 11.1.2 从检查点恢复状态11.1.3 检查点算法…

linux 内存寻址

&#xff08;持续更新&#xff09; 相关概念 查看的书籍为 深入linux内核 内存地址 当使用80x86&#xff08;32位&#xff09;微处理器时&#xff0c;一般分为三种不同的地址&#xff1a; 逻辑地址 包含在机器语言指令中用来指定一个操作数或一条指令的地址。每一个逻辑地址…