【算法】字符串的排列
难度:中等
给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。
换句话说,s1 的排列之一是 s2 的 子串 。
示例 1:
输入:s1 = “ab” s2 = “eidbaooo”
输出:true
解释:s2 包含 s1 的排列之一 (“ba”).
示例 2:
输入:s1= “ab” s2 = “eidboaoo”
输出:false
提示:
1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
解题思路:
滑动窗口是处理字符串子串问题时常用的技术,通过在字符串上移动一个固定大小的窗口来检查不同的子串。我们的目标是检查字符串s2中是否存在s1所有字符的一个排列作为子串。
- 计数映射:首先,我们需要统计字符串s1中每个字符出现的次数,可以用一个对象或Map来实现。这将帮助我们后续比较时,快速判断一个子串是否为s1的排列。
- 滑动窗口:在s2上建立一个大小与s1相等的窗口,初始时覆盖s2的前|s1|个字符(|s1|表示字符串s1的长度)。然后,逐步将窗口向右滑动一位,每次滑动时:
- 增加新进入窗口的字符的计数。
- 减少离开窗口的字符的计数。
- 检查当前窗口内的字符计数是否与s1的计数映射完全匹配,如果匹配,则找到了一个排列子串,返回true。
- 遍历结束未找到:如果遍历完s2仍未找到匹配的子串,则返回false。
JavaScript实现:
/*** @param {string} s1* @param {string} s2* @return {boolean}*/
var checkInclusion = function (s1, s2) {if (s1.length > s2.length) return false; // s1长度大于s2,不可能为子串// 计算s1中各字符的计数const countMap = new Map();for (const char of s1) {countMap.set(char, (countMap.get(char) || 0) + 1);}console.log(countMap)// 定义滑动窗口的大小const windowSize = s1.length;// 循环遍历的时候一定要记住减去for (let i = 0; i <= s2.length - windowSize; i++) {// 重置滑动窗口的计数映射,为什么要重置滑动窗口?是因为在下面的for j循环中对tempMap进行改动,所以在每次for i循环中都需要对tempMap进行重置const tempMap = new Map(countMap);console.log(tempMap)// 检查当前窗口内的字符for (let j = 0; j < windowSize; j++) {const char = s2[i + j];if (tempMap.has(char)) {tempMap.set(char, tempMap.get(char) - 1);// 如果计数为0,可以从映射中移除if (tempMap.get(char) === 0) tempMap.delete(char);} else { // 如果不是的话,一定要跳出循环,要不然执行会超时break; // 当前字符不在s1的映射中,直接跳出循环}}// 如果映射为空,说明当前窗口内的字符与s1的排列一致if (tempMap.size === 0) return true;}return false; // 遍历结束,未找到匹配的子串
};
console.log(checkInclusion("ab", "eidbaooo")); // 输出: true
相关文章:
【算法】字符串的排列
难度:中等 给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。 换句话说,s1 的排列之一是 s2 的 子串 。 示例 1: 输入:…...
5-3.损失函数
文章最前: 我是Octopus,这个名字来源于我的中文名–章鱼;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ;这博客是记录我学习的点点滴滴,如果您对 Python、Java、AI、算法有兴趣,可以关注我的…...

SCSA第四天
ASPF FTP --- 文件传输协议 Tftp --- 简单文件传输协议 FTP协议相较于Tftp协议 ---- 1,需要进行认证 2,拥有一套完整的命令集 用户认证 防火墙管理员认证 ---- 校验登录者身份合法性 用户认证 --- 上网行为管理中的一环 上网用户认证 --- 三层认证…...

品牌策划必读:9本改变游戏规则的营销经典
作为深耕品牌十余年的策划人,这些年自学啃下的书不计其数。 这里特意挑选了几本知名度不高但是却非常有用的“遗珠”优质品牌策划书籍分享出来。 如果你是一位初步了解品牌的人,这些书籍既包含了品牌理论基础,也有实用的实践指导。 这些书…...

泛型
背景 优点 类型绝对安全避免强制类型转换 泛型类 定义 使用 举例 泛型类 // 泛型类 T就是类型参数 public class Generic<T>{// key这个成员变量的类型为T,T的类型由外部指定private T t;public void set(T t){this.t t;}public T get(){return t;} }使用 // 创建一个泛…...
react动态渲染列表与函数式组件
1.如何使用jsx语法动态渲染列表呢,下边我用一个例子来切实总结一下 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scal…...

小程序内容管理系统设计
设计一个小程序内容管理系统(CMS)时,需要考虑以下几个关键方面来确保其功能完善、用户友好且高效: 1. 需求分析 目标用户:明确你的目标用户群体,比如企业、媒体、个人博主等,这将决定系统的功…...

HDFS 块重构和RedundancyMonitor详解
文章目录 1. 前言2 故障块的重构(Reconstruct)2.1 故障块的状态定义和各个状态的统计信息2.2 故障文件块的查找收集2.5.2.1 misReplica的检测2.5.2.2 延迟队列(postponedMisreplicatedBlocks)的构造和实现postponedMisreplicatedBlocks中Block的添加postponedMisreplicatedBloc…...

Power BI DAX常用函数使用场景和代码示例
Power BI函数表达式对于没有接触过的朋友可能会有些迷茫,花一点时间了解一下原理在学习一些常用的DAX函数,就可以解决工作中绝大部分问题,函数使用都是共同的。 以下是一些最常用的DAX函数,如聚合,计数,日期…...

机器学习与深度学习:区别与联系(含工作站硬件推荐)
一、机器学习与深度学习区别 机器学习(ML:Machine Learning)与深度学习(DL:Deep Learning)是人工智能(AI)领域内两个重要但不同的技术。它们在定义、数据依赖性以及硬件依赖性等方面…...
大模型/NLP/算法面试题总结5——Transformer和Rnn的区别
Transformer 和 RNN(循环神经网络)是两种常见的深度学习模型,广泛用于自然语言处理(NLP)任务。 它们在结构、训练方式以及处理数据的能力等方面有显著的区别。以下是它们的主要区别: 架构 RNN࿰…...

【RHCE】转发服务器实验
1.在本地主机上操作 2.在客户端操作设置主机的IP地址为dns 3.测试,客户机是否能ping通...

AI提示词:打造爆款标题生成器
打开GPT输入以下内容: # Role 爆款标题生成器## Profile - author: 姜小尘 - version: 02 - LLM: Kimi - language: 中文 - description: 利用心理学和市场趋势,生成吸引眼球的自媒体文章标题。## Background 一个吸引人的标题是提升文章点击率和传播力…...

skywalking-1-服务端安装
skywalking很优秀。 安装服务端 skywalking的服务端主要是aop服务,为了方便查看使用还需要安装ui。另外采集的数据我们肯定要存起来,这个数据库就直接用官方的banyandb。也就是aop、ui、banyandb都使用官方包。 我们的目的是快速使用和体验,…...

查看oracle ojdbc所支持的JDBC驱动版本
oracle jcbc驱动的下载地址参考:JDBC and UCP Downloads page 其实上文中对ojdbc所支持的JDBC驱动版本已经有说明了,不过,因为oracle的驱动包很多时间,都是在公司内部私服里上传维护的,上传的时候,可能又没…...

自媒体运营怎样引流客源?
不管是企业还是个人,越来越多都在做自媒体引流运营,那有什么引流客源的方式呢? 高质量内容:创作并分享有价值的内容,吸引目标受众,提升内容的分享和传播效果。 SEO优化:优化文章标题、关键词和…...
【算法】十进制转换为二进制
目的:将十进制转换为二进制 思路: 首先我们手算的情况是通过求余数算出进制数,同样代码也是通过做除法和求余数的方式,除法是得出下一次的被除数,而求余数是得到进制数 代码: #include<stdio.h>/…...
Postman中的API安全堡垒:全面安全性测试指南
🛡️ Postman中的API安全堡垒:全面安全性测试指南 在当今的数字化世界中,API安全性是保护数据和系统不可或缺的一环。Postman作为API开发和测试的领先工具,提供了多种功能来帮助开发者进行API安全性测试。本文将深入探讨如何在Po…...

学圣学最终的目的是:达到思无邪的状态( 纯粹、思想纯正、积极向上 )
学圣学最终的目的是:达到思无邪的状态( 纯粹、思想纯正、积极向上 ) 中华民族,一直以来,教学都是以追随圣学为目标,所以中华文化也叫圣学文化,是最高深的上等学问; 圣人那颗心根本…...

JS进阶-构造函数
学习目标: 掌握构造函数 学习内容: 构造函数 构造函数: 封装是面向对象思想中比较重要的一部分,js面向对象可以通过构造函数实现的封装。 同样的将变量和函数组合到了一起并能通过this实现数据的共享,所不同的是借助…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...

(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.
这个警告表明您在使用Vue的esm-bundler构建版本时,未明确定义编译时特性标志。以下是详细解释和解决方案: 问题原因: 该标志是Vue 3.4引入的编译时特性标志,用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...
使用python进行图像处理—图像滤波(5)
图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值,以达到平滑(去噪)、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算,…...