【算法】字符串的排列
难度:中等
给你两个字符串 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实现数据的共享,所不同的是借助…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...

基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)
引言 在嵌入式系统中,用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例,介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单,执行相应操作,并提供平滑的滚动动画效果。 本文设计了一个…...