每日一题 — 找到字符串中所有字母异位词

解法一:暴力枚举

解法二:滑动窗口+hash表优化

  • 定义left和right为起始坐标0,right向后遍历,并加入到哈希表中,
  • 然后也要记录下来每次进入哈希表的有效字符(与目标字符串中相同的字符)的个数
  • 且这个滑动窗口的长度不能超过目标字符串的长度
  • 当超过的时候, left向后移动,且维护count的值

代码:

public List<Integer> findAnagrams(String ss, String pp) {
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26];
        //统计p中的字符的个数
        for(char ch : p){
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];
        int m = p.length;
        List<Integer> ret = new ArrayList<>();
        for(int left = 0, right = 0,count = 0; right < s.length; right++){
            //进窗口
            char in = s[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']){
                //维护count
                count++;
            }
            //判断
            if(right - left + 1 > m){
                //出窗口
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']){
                    //维护count
                    count--;
                }
            }
            if(count == m){
                ret.add(left);
            }
        }
        return ret;
    }

 

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

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

相关文章

C++修炼之路之list模拟实现--C++中的双向循环链表

目录 引言 一&#xff1a;STL源代码中关于list的成员变量的介绍 二&#xff1a;模拟实现list 1.基本结构 2.普通迭代器 const迭代器的结合 3.构造拷贝构造析构赋值重载 清空 4.inserterase头尾插入删除 5.打印不同数据类型的数据《使用模板加容器来完成》 三&#xf…

SQLite、MySQL 和 PostgreSQL 数据库速度比较(本文阐述时间很早比较,不具有最新参考性)(二十五)

返回&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;用于 SQLite 的异步 I/O 模块&#xff08;二十四&#xff09; 下一篇&#xff1a;SQLite—系列文章目录 注意&#xff1a;本文档非常非常旧。它描述了速度比较 SQLite、MySQL 和 PostgreSQL 的古老版本。 这里…

学习一门语言的方法和套路(B站转述)

视频链接 up虽然长相英(ping)俊(ping)&#xff0c;但是讲的干活&#xff0c;没恰饭。 学习流程&#xff1a; 1.快速阅读&#xff0c;掌握概况 2.深入细节内容 例如&#xff1a;java (JDBC)、html 、netty 不管三七二十一&#xff0c;先了解套路&#xff0c;再深入研究。 高…

安装CUDNN详细过程

cuDNN&#xff08;CUDA Deep Neural Network library&#xff09;是由NVIDIA开发的深度学习GPU加速库。 cuDNN包含了许多针对神经网络操作进行高度优化的函数&#xff0c;旨在使深度学习框架能够在NVIDIA的GPU上实现最佳性能&#xff0c;这个库提供了高效计算和加速&#xff0c…

牛客网刷题 :BC50 你是天才吗

描述 据说智商140以上者称为天才&#xff0c;KiKi想知道他自己是不是天才&#xff0c;请帮他编程判断。输入一个整数表示一个人的智商&#xff0c;如果大于等于140&#xff0c;则表明他是一个天才&#xff0c;输出“Genius”。 输入描述&#xff1a; 多组输入&#xff0c;每…

在 PyCharm 中使用系统安装的 Python 和 Anaconda 的 Python什么区别

virtualenv environment &#xff1a; virtualenv 是一个用于创建独立 Python 环境的工具。它可以在同一个系统上创建多个相互独立的 Python 环境&#xff0c;每个环境都有自己的 Python 解释器和包库&#xff0c;从而可以实现不同项目之间的依赖隔离和版本控制。coda environm…

vue快速入门(二十五)本地存储与初始化使用

注释很详细&#xff0c;直接上代码 上一篇 新增内容 本地获取数据数据存储到本地 源码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial…

2024蓝桥杯——宝石问题

先展示题目 声明 以下代码仅是我的个人看法&#xff0c;在自己考试过程中的优化版&#xff0c;本人考试就踩了很多坑&#xff0c;我会—一列举出来。代码可能很多&#xff0c;但是总体时间复杂度不高只有0(N) 函数里面的动态数组我没有写开辟判断和free&#xff0c;这里我忽略…

频率域滤波基础(离散傅里叶变换使用填充的缺陷)

本来是个很简单的问题&#xff0c;作者硬是写的这么复杂&#xff0c;翻译还搞错了。重点是我发现作者真正有用的东西没讲到&#xff0c;比如相位和谱如何影响图像。连个转换公式都没有&#xff0c;我只能说作者是在混字数。 首先看关于中心对称是什么意思&#xff1f;我木太明白…

MySql 视图 存储过程 触发器

文章目录 视图数据库对象视图的理解创建、查看、更新、删除 存储过程和存储函数概述分类存储过程的创建和调用存储函数的创建和调用存储过程和存储函数的对比存储过程和存储函数的查看、修改、删除 变量GLOBAL 与 SESSION 变量的使用会话用户变量和局部变量的使用 定义条件与处…

【机器学习300问】70、向量化技术来计算神经网络时维度如何确保正确?

一、向量化技术在进行神经网络计算时的优势 向量化是一种优化技术&#xff0c;通过使用数组操作代替for循环&#xff0c;可以大大提高代码的性能和效率。在深度学习中尤其明显&#xff0c;可以提高计算效率、简化代码、优化内存使用。 二、如何确保计算时维度是正确的&#xf…

中标了,Trojan/Hijack.v木马病毒怎么解决?

火绒只是提示有病毒木马&#xff0c;并未解决。 经过不断尝试.。。。。。。 往下拉找到 Internet选项 连接 – 局域网设置 把前面的勾选取消 发现以上办法网络上出现的搜索注册表关键字等办法都无法解决。。。 解决方法一&#xff1a; 电脑进入安全模式&#xff0c;然后进…

【vue】v-model 双向数据绑定

:value&#xff1a;单向数据绑定v-model&#xff1a;双向数据绑定 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0">…

STM32 MPU配置参数

TXE LEVEL一般只用MPU_TEX_LEVEL0 1 - 1 - 1 -0性能最强&#xff08;TEX - C - B- S&#xff09;. #define MPU_TEX_LEVEL0 ((uint8_t)0x00) #define MPU_TEX_LEVEL1 ((uint8_t)0x01) #define MPU_TEX_LEVEL2 ((uint8_t)0x02) 基于上表进行常用配置 &#xff…

Wpf 使用 Prism 实战开发Day19

待办事项功能页面完善以及优化 概要&#xff1a; 由于待办事项功能页&#xff0c;数据已正常渲染出来了。但页面新增&#xff0c;查询&#xff0c;修改&#xff0c;删除等功能还未实现。本章节来实现页面的请求后台实现CURD&#xff08;增删改查&#xff09; 一.待办事项查询…

泰迪智能科技携手韩山师范学院“企业微专业合作办学招生宣讲”圆满结束

为进一步深化校企合作&#xff0c;落实高校应用型人才培养。2024年4月11日&#xff0c;泰迪智能科技携手韩山师范学院开展企业微专业合作办学招生宣讲会在韩山师范学院顺利举行&#xff0c;本次宣讲会旨在与韩山师范学院学子深入讲解数字经济时代下的企业用工需求&#xff0c;着…

ins视频批量下载,instagram批量爬取视频信息

简介 Instagram 是目前最热门的社交媒体平台之一,拥有大量优质的视频内容。但是要逐一下载这些视频往往非常耗时。在这篇文章中,我们将介绍如何使用 Python 编写一个脚本,来实现 Instagram 视频的批量下载和信息爬取。 我们使用selenium获取目标用户的 HTML 源代码,并将其保存…

数据结构 -- 二分查找

本文主要梳理了二分查找算法的几种实现思路&#xff0c;基本概念参考 顺序、二分、哈希查找的区别及联系_生成一个大小为10万的有序数组,随机查找一个元素,分别采用顺序查找和二分查找方式-CSDN博客 1、基本概念 &#xff08;1&#xff09;前提条件&#xff1a;待查找数据必须…

解决调用相同url数据不刷新问题

原代码 原因 谷歌浏览访问相同接口默认调用缓存数据 解决方案 添加时间戳

WebKit简介及工作流程

文章目录 一、WebKit简介二、WebKit结构三、Webkit工作流程四、WebKit常见问题五、WebKit优点六、相关链接 一、WebKit简介 WebKit是一个开源的浏览器引擎&#xff0c;它的起源可以追溯到2001年&#xff0c;当时苹果公司推出了其首款基于Unix的操作系统Mac OS X。在2002年&…