【算法】滑动窗口——找到字符串中所有字母异位词

本节博客是对题目——找到字符串中所有字母异位词的从读题到代码实现以及优化的详细解读,有需要借鉴即可。

目录

  • 1.题目
  • 2.滑动窗口 + 哈希数组
  • 3.异位词优化
  • 4.总结

1.题目

题目链接:LINK
在这里插入图片描述

首先来解释一下什么是异位词,所谓“异位词”,即不要求字母顺序的字符串。

其实这个题目思路很快就可以想到,拿个left,right指针,使两者间距始终等于p字符串长度,再与p字符串对比一下就行了。

说起来这个思路那不就是“滑动窗口”嘛,因为两个指针都是从左到右移动的。
那异位怎么进行比较的呢?可以搞一个哈希数组进行依次比较即可。

2.滑动窗口 + 哈希数组

于是,我们可以写出下面的代码:

class Solution
{
public:
 bool check(int* p, int*s)
 {
    for(int i = 0;i < 128;i++)
    {
        if(p[i] != s[i])
        {
            return false;
        }
    }

    return true;
 }
 vector<int> findAnagrams(string s, string p) 
 {
    //统计一下p字符串的字符信息
    size_t len = p.size();
    int hash_p[128] = {0};
    for(int i = 0;i<len;i++)
    {
        hash_p[p[i]]++;
    }

    int n = s.size();
    int hash_s[128] = {0};
    vector<int> ret;
    //滑动窗口
    for(int right = 0,left = 0;right < n;right++)
    {
        //进窗口
        hash_s[s[right]]++;

        //判断,出窗口
        if(right - left + 1 > len)
        {
            hash_s[s[left]]--;
            left++;
        }

        //更新结果
        if(check(hash_p,hash_s) && right - left + 1 == len)
        {
            ret.push_back(left);
        }
    }

    return ret;
 }
};

实际上,题目中明确说只有小写字母,所以说可以把哈希数组搞成26个的:


class Solution
{
public:
    bool check(int* p, int* s)
    {
        for (int i = 0; i < 26; i++)
        {
            if (p[i] != s[i])
            {
                return false;
            }
        }

        return true;
    }

    vector<int> findAnagrams(string s, string p)
    {
        //统计一下p字符串的字符信息
        size_t len = p.size();
        int hash_p[26] = { 0 };
        for (int i = 0; i < len; i++)
        {
            hash_p[p[i] - 'a']++;
        }

        int n = s.size();
        int hash_s[26] = { 0 };
        vector<int> ret;
        //滑动窗口
        for (int right = 0, left = 0; right < n; right++)//"cbaebabacd"
        {
            //进窗口
            hash_s[s[right] - 'a']++;

            //判断,出窗口
            if (right - left + 1 > len)
            {
                hash_s[s[left] - 'a']--;
                left++;
            }

            //更新结果
            if (check(hash_p, hash_s) && right - left + 1 == len)
            {
                ret.push_back(left);
            }
        }

        return ret;
    }
};

3.异位词优化

虽然这样可以解题,不过问题是如果是比较的是比较多的字符呢?不仅仅是26的小写字母。我想如果这样比较,复杂度瞬间就会上来了。

所以,在比较异位词时,我们需要再优化一下:
思路大致是下面这样的,如下:
在这里插入图片描述
所以,可以优化为下面代码:


class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        //统计一下p字符串的字符信息
        size_t len = p.size();
        int hash_p[26] = { 0 };
        for (int i = 0; i < len; i++)
        {
            hash_p[p[i] - 'a']++;
        }

        int n = s.size();
        int count = 0;//count标识有效字符的个数,即p字符串的长度
        int hash_s[26] = { 0 };
        vector<int> ret;
        //滑动窗口
        for (int right = 0, left = 0; right < n; right++)//"cbaebabacd"
        {
            //进窗口
            hash_s[s[right] - 'a']++;
            if(hash_s[s[right]-'a'] <= hash_p[s[right]-'a'])count++;//进窗口,维护有效字符个数

            //判断,出窗口
            if (right - left + 1 > len)
            {
                if(hash_s[s[left] - 'a'] <= hash_p[s[left] - 'a'])count--;//出窗口,维护有效字符个数
                hash_s[s[left] - 'a']--;
                left++;
            }

            //更新结果
            if (count == len)
            {
                ret.push_back(left);
            }
        }

        return ret;
    }
};

4.总结

其实总结一下来看,这个题目除了异位词问题之外也没什么东西,这个题目是一个典型的“固定长度的滑动窗口”,要解出来难度不大。


EOF

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

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

相关文章

JavaWeb文件上传/下载(Servlet)

效果 文件下载 文件上传 项目概述 Jakarta EE9&#xff0c;Web项目 项目文件结构 0 maven依赖&#xff0c;资源文件 <!-- lombok插件--> <dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId&g…

最新的云渲染100活动有哪些?渲染100邀请码1a12

随着科技的进步&#xff0c;云渲染已经成为设计行业的必备工具&#xff0c;各个云渲染平台为了吸引用户也推出各种各样的活动&#xff0c;今天我们以广受好评的渲染100为例&#xff0c;来说下它们的活动体系。 1、新用户活动 渲染100对新用户很友好&#xff0c;提供了充足的测…

欢乐钓鱼大师攻略,怎么获取道具?

在《欢乐钓鱼大师》的游戏世界中&#xff0c;道具是提升钓鱼体验、解锁新功能以及完成挑战的关键。通过多种方式获取道具&#xff0c;能够帮助玩家更好地探索游戏世界、挑战自我&#xff0c;以及与其他玩家展开竞争。以下是关于如何获取道具的详细攻略&#xff0c;让你能够在游…

AI写作推荐-写文ai-AI在线写作生成器-3步完成写作任务

AI写作利器&#xff1a;推荐几款神助攻文案创作工具 随着技术的进步&#xff0c;人工智能&#xff08;AI&#xff09;已达到高级水平&#xff0c;在众多领域展现其强大能力。 在文本创作的领域&#xff0c;人工智能&#xff08;AI&#xff09;应用已显著地提升了写作效率和创意…

Java后端实现对象与文件接收数据(minio测试)

实现思路&#xff1a; 1. 两个接口实现&#xff0c;一个接对象数据(file)&#xff0c;一个接文件数据(json)。 2. json对象(base64String) 实体类信息 &#xff0c;请求体统一接收 3. file, String name ,String password ,String name &#xff0c; Controller层接收 统一…

环形链表(给定一个链表的头节点 head ,返回链表开始入环的第一个节点)的原理讲解

一&#xff1a;题目 二&#xff1a;原理讲解 解决这个题目 &#xff0c;我们得先理解它的原理。 1&#xff1a; 首先假设两个指针&#xff0c;一个快指针fast&#xff0c;一个慢指针slow&#xff0c;fast一次移动两个节点&#xff0c;slow一次移动一个节点。&#xff08;前面…

MF自定义控件方法

在MFC中&#xff0c;您可以通过自定义控件来实现特定的用户界面元素或功能&#xff0c;以满足您的应用程序需求。自定义控件通常是从CWnd类派生的子类&#xff0c;您可以在其中重写绘制、处理事件等方法&#xff0c;以实现您想要的功能和外观。以下是一般步骤&#xff1a; 创建…

【Java】变量类型

类变量&#xff1a;独立于方法之外的变量&#xff0c;用static修饰实例变量&#xff1a;独立于方法之外的变量&#xff0c;不过没有static修饰局部变量&#xff1a;类的方法中的变量 示例1&#xff1a; public class test_A {static int a;//类变量(静态变量)String b;//实例…

【JAVA进阶篇教学】第十篇:Java中线程安全、锁讲解

博主打算从0-1讲解下java进阶篇教学&#xff0c;今天教学第十篇&#xff1a;Java中线程安全、锁讲解。 当涉及到多线程编程时&#xff0c;保证线程安全是至关重要的。线程安全意味着在多个线程访问共享资源时&#xff0c;不会发生数据错乱或不一致的情况。为了实现线程安全&am…

问题:幂等性 分布式session

web项目中请求线程到service层的时候远程调用服务之前是串行化执行每个任务都要get阻塞等待任务完成&#xff0c;举例当用户在购物车页面点击去结算就会请求后台toTrade请求获取订单确认的详情数据并渲染到订单详情页&#xff0c;现在在toTrade请求中使用异步任务编排Completab…

微信授权登录02-移动端

目录 ## 前言 1.准备工作 1.1 网站域名 1.2 微信公众号 2.授权登录开发 2.1 前端开发 2.1.1 调起微信授权页面 ## 调起微信授权页面效果图 2.1.2 用户允许授权后回调处理 2.2 后端开发 2.2.1 根据code查询用户信息 2.2.2 自动注册登录 ## 后记 ## 前言 上一篇写…

Nios-II编程入门实验

文章目录 一 Verilog实现流水灯二 Nios实现流水灯2.1 创建项目2.2 SOPC添加模块2.3 SOPC输入输出连接2.4 Generate2.5 软件部分2.6 运行结果 三 Verilog实现串口3.1 代码3.2 引脚3.3 效果 四 Nios2实现串口4.1 sopc硬件设计4.2 top文件4.3 软件代码4.4 实现效果 五 参考资料六 …

nodeJs用ffmpeg直播推流到rtmp服务器上

总结 最近在写直播项目 目前比较重要的点就是推拉流 自己也去了解了一下 ffmpeg FFmpeg 是一个开源项目&#xff0c;它提供了一个跨平台的命令行工具&#xff0c;以及一系列用于处理音频和视频数据的库。FFmpeg 能够执行多种任务&#xff0c;包括解封装、转封装、视频和音频…

Ps各种修改文字超实用方法

介绍 在日常生活中,难免会遇到进行文字修改的ps场景,此时就需要用到比较专业的ps进行文字修改,博主特意整合了多种情况下的文字p图方法进行记录,但是不包含全部情况,只记录日常中常见的情况,也可以解决大部分场景了 原图有可用文字素材 在p图时,我们可以先观察我们要p的图中…

【ARMv8/v9 系统寄存器 5 -- CPU ID 判断寄存器 MPIDR_EL1 使用详细介绍】

文章目录 寄存器名称: MPIDR_EL1寄存器结构:主要功能和用途亲和级别&#xff08;Affinity Levels&#xff09;简介CORE ID 获取函数 在ARMv8-A架构中&#xff0c; MPIDR_EL1寄存器是一个非常重要的系统寄存器&#xff0c;它提供了关于处理器在其物理和逻辑配置中的位置的信息。…

Linux下安装JDK并配置环境变量

一、Oracle官网下载jdk 1、官网地址 https://www.oracle.com/java/technologies/downloads/#java17 2、命令下载 wget https://download.oracle.com/java/17/latest/jdk-17_linux-x64_bin.tar.gz 3、解压 tar -zxvf jdk-17_linux-x64_bin.tar.gz 4、配置环境变量 ec…

webrtc windows 编译,以及peerconnection_client

webrtc windows环境编译&#xff0c;主要参考webrtc官方文档&#xff0c;自备梯子 depot tools 安装 Install depot_tools 因为我用的是windows&#xff0c;这里下载bundle 的安装包&#xff0c;然后直接解压&#xff0c;最后设置到环境变量PATH。 执行gn等命令不报错&…

SQLite .journal 文件

在之前插入大量数据测试的时候&#xff0c;发现在数据库文件同级目录下会产生一个同名.journal的文件&#xff0c;并且不是一直会存在&#xff0c;而是生成一会就会自动删除&#xff0c;然后继续生成继续删除&#xff0c;直到数据插入完成。 初步猜测&#xff0c;应该是类似 re…

rust开发web服务器框架,github排名对比

Rocket Star最多的框架 github仓库地址&#xff1a;GitHub - rwf2/Rocket: A web framework for Rust. Rocket 是一个针对 Rust 的异步 Web 框架&#xff0c;重点关注可用性、安全性、可扩展性和速度。 Axum 异步运行时 githuh仓库地址&#xff1a;GitHub - tokio-rs/axum: …

Unity开发中导弹路径散射的原理与实现

Unity开发中导弹路径散射的原理与实现 前言逻辑原理代码实现导弹自身脚本外部控制脚本 应用效果结语 前言 前面我们学习了导弹的追踪的效果&#xff0c;但是在动画或游戏中&#xff0c;我们经常可以看到导弹发射后的弹道是不规则的&#xff0c;扭扭曲曲的飞行&#xff0c;然后击…