【leetcode系列】567.字符串的排列(滑动窗口)
题目
给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。
换句话说,s1 的排列之一是 s2 的 子串 。
示例
示例 1:
输入:s1 = “ab” s2 = “eidbaooo”
输出:true
解释:s2 包含 s1 的排列之一 (“ba”).
示例 2:
输入:s1= “ab” s2 = “eidboaoo”
输出:false
思路1:dfs
使用集合统计s1的所有可能排列结果,然后挨个遍历,看是否在s2中
- 简单粗暴
- 容易超时
思路2:滑动窗口
前提:abc排列结果集6种:[abc,acb,bca,bac,cab,cba]。但是无论怎么排列,6种结果集中,一定是根据元素abc三个字符排列的。
所以,如果s1 = “abc”,我们只要判断s2中长度 = 3(abc的长度)的subStr子串,是否有包含abc三个字符的。有则说明包括。
比如s2 = “bbbca”,其中长度为3的子串bca,就由abc三个字符组成。所以就包含
步骤:
1、确定s1的长度len
2、使用滑动窗口,在s2中,扩张到len
- 此时,s1
- s2的子串sub2
3、判断:s2的subStr子串,是否由s1中字符组成 :使用map判断
mapS1
- key:字符
- val:每个字符出现的次数
- abc:(a-1,b-1,c-1)
mapSub2
- key:字符
- val:每个字符出现的次数
- bbb(b-3)
如果mapS1中的所有key集合
key - v1
key - v2
都满足 v1 == v2,也就是说s1中的每个字符,都在sub2中,而且每个字符出现的频率和sub2一样,则说明s2的subStr子串,是由s1中字符组成的
4、举例:
s1:abc
s2:bbbca
- 第一个sub2:bbb,显然mapS1中(a-1,b-1,c-1),而mapS2中(b-3),不满足
- 窗口滑动得到第二个sub2:bbc,显然mapS2中(b-2,c-1),不满足
- 窗口滑动得到第三个sub2:bca,显然mapS2中(b-1,c-1,a-1),满足。
和mapS1中每个元素,对应的val值(出现频率)都一样。说明找到了!
public class CheckS1DfsInS2 {public static void main(String[] args) {boolean b = checkInclusion("abc", "bbbca");System.out.println(b);}private static boolean checkInclusion(String s1, String s2) {if (s1 == null || s1.length() == 0) {return true;}if (s2 == null || s2.length() == 0 || s2.length() < s1.length()) {return false;}if (s1.length() == 1) {return s2.contains(s1);}Map<Character, Integer> mapS1 = new HashMap<>();int len1 = s1.length();for (int i = 0; i < len1; i++) {mapS1.merge(s1.charAt(i), 1, Integer::sum);}// 扩张到len1 - 1int i = 0;Map<Character, Integer> mapS2 = new HashMap<>();while (i < s1.length() - 1) {mapS2.merge(s2.charAt(i), 1, Integer::sum);i ++;}i = 0;for (int j = len1 - 1; j < s2.length(); j++) {mapS2.merge(s2.charAt(j), 1, Integer::sum);if (contain(mapS1, mapS2, s1)) {return true;} else {// 滑动char start = s2.charAt(i);Integer v2 = mapS2.get(start);mapS2.put(start, v2 - 1);i ++;}}return false;}private static boolean contain(Map<Character, Integer> mapS1, Map<Character, Integer> mapS2, String s1) {for (int k = 0; k < s1.length(); k++) {char s1Key = s1.charAt(k);Integer v1 = mapS1.get(s1Key);Integer v2 = mapS2.get(s1Key);if (v2 == null || ! v2.equals(v1)) {return false;}}return true;}
}
相关文章:
【leetcode系列】567.字符串的排列(滑动窗口)
题目 给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。 换句话说,s1 的排列之一是 s2 的 子串 。 示例 示例 1: 输入:s1 “ab” s2…...
情感分析方法与实践
第1关:情感分析的基本方法 情感分析简介 情感分析,又称意见挖掘、倾向性分析等。简单而言,是对带有情感色彩的主观性文本进行分析、处理、归纳和推理的过程。在日常生活中,情感分析的应用非常普遍,下面列举几种常见的…...
迁移学习——CycleGAN
CycleGAN 1.导入需要的包2.数据加载(1)to_img 函数(2)数据加载(3)图像转换 3.随机读取图像进行预处理(1)函数参数(2)数据路径(3)读取文…...
【软件测试】对于测试中的bug,我们真正了解了吗?
目录 1.软件测试的生命周期 1.1.软件测试阶段流程 1.2.各流程的任务 2.什么是bug 2.1.bug的概念 2.2.怎么描述bug 2.3.bug的级别 2.4.bug的生命周期 1.软件测试的生命周期 在学习bug前,我们先来学习一下软件测试的生命周期,也就是测试人员进行测…...
Packer-Fuzzer一款好用的前端高效安全扫描工具
★★免责声明★★ 文章中涉及的程序(方法)可能带有攻击性,仅供安全研究与学习之用,读者将信息做其他用途,由Ta承担全部法律及连带责任,文章作者不承担任何法律及连带责任。 1、Packer Fuzzer介绍 Packer Fuzzer是一款针对Webpack…...
解决卸载TabX explorer软件后导致系统文件资源管理器无法正常使用问题
最近安装了最新版本的鲁大师,安装过程中不小心同时安装了捆绑软件TabX explorer。这个软件和系统自带的文件资源管理器很像,最后弹出会员到期才发现,这个不是系统文件资源管理器,是第三方的文件资源管理器,就按正常流程…...
qt for android 使用打包sqlite数据库文件方法
1.在使用sqlite数据库时,先将数据库文件打包,放置在assets中如下图: 将文件放置下android中的assets下的所有文件都会打包在APK中,可以用7zip查看apk文件 2.在qt代码读取数据文件,注意在assets下的文件都是Read-Only,需…...
MYBATIS大于等于、小于等于的写法
mybatis使用的是xml格式的文件。使用>和<号的时候,会存在与xml的标签的规范冲突。需要写成如下形式,否则会报错。 第一种写法 原符号 替换符号 < < < <> > > >& & &…...
基于堆叠长短期记忆网络 Stacked LSTM 预测A股股票价格走势
前言 系列专栏:【深度学习:算法项目实战】✨︎ 涉及医疗健康、财经金融、商业零售、食品饮料、运动健身、交通运输、环境科学、社交媒体以及文本和图像处理等诸多领域,讨论了各种复杂的深度神经网络思想,如卷积神经网络、循环神经网络、生成对…...
SpringCloud Alibaba Sentinel基础入门与安装
GitHub地址:https://github.com/alibaba/Sentinel 中文文档:https://sentinelguard.io/zh-cn/docs/introduction.html 下载地址:https://github.com/alibaba/Sentinel/releases Spring Cloud Alibaba 官方说明文档:Spring Clou…...
Arduino IDE下载、安装和配置
文章开始先把我自己网盘里的安装包分享给大家,链接:https://pan.baidu.com/s/1cb2_3m0LnuSKLnWP_YoWPw?pwdwwww 提取码:wwww 里面一个是Arduino IDE的安装包,另一个是即将发布的版本。 第一个安装包打开直接按照我的步骤安装就…...
SOBEL图像边缘检测器的设计
本项目使用FPGA设计出SOBEL图像边缘检测器,通过分析项目在使用过程中的工作原理和相关软硬件设计进行分析详细介绍SOBEL图像边缘检测器的设计。 资料获取可联系wechat 号:comprehensivable 边缘可定义为图像中灰度发生急剧变化的区域边界,它是图像最基本…...
Day35:2734. 执行字串操作后的字典序最小字符串
Leetcode 2734. 执行字串操作后的字典序最小字符串 给你一个仅由小写英文字母组成的字符串 s 。在一步操作中,你可以完成以下行为: 选择 s 的任一非空子字符串,可能是整个字符串,接着将字符串中的每一个字符替换为英文字母表中的前…...
【高考志愿】机械工程
目录 一、专业概述 二、学科特点 三、就业前景 四、机械工程学科排名 五、专业选择建议 高考志愿选择机械工程,这是一个需要深思熟虑的决定,因为它不仅关乎未来的学习和职业发展,更是对自我兴趣和潜能的一次重要考量。 一、专业概述 机…...
ffmpeg将mp4转换为swf
文章目录 ffmpeg安装、配置java运行报错 Cannot run program "ffmpeg" ffmpeg命令mp4转为swf示例 ### ffmpeg -i input.mkv -b:v 600 -c:v libx264 -vf scale1920:1080 -crf 10 -ar 48000 -r 24 output.swfmkv转为swf示例 其他文档命令参数简介 需要将mp4转换为swf&a…...
论文学习 --- RL Regret-based Defense in Adversarial Reinforcement Learning
前言 个人拙见,如果我的理解有问题欢迎讨论 (●′ω`●) 原文链接:https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p2633.pdf 研究背景 深度强化学习(Deep Reinforcement Learning, DRL)在复杂和安全关键任务中取得了显著成果,例如自动驾驶。然而,DRL策略容易受…...
【Linux小命令】一文讲清ldd命令及使用场景
一文讲清ldd命令及使用场景 前言下面进入正题:ldd命令 前言 博主今天ubuntu编译go项目出来的一个可执行文件,放centos运行发现居然依赖于XXlib库。然后我一下就想到两个系统库版本不一致,重编。换系统,导项目,配环境……...
自费5K,测评安德迈、小米、希喂三款宠物空气净化器谁才是高性价比之王
最近,家里的猫咪掉毛严重,简直成了一个活生生的蒲公英,家中、空气中各处都弥漫着猫浮毛甚至所有衣物都覆盖着一层厚厚的猫毛。令人难以置信的是,有时我甚至在抠出的眼屎中都能发现夹杂着几根猫毛。真的超级困扰了。但其实最空气中…...
1373. 二叉搜索子树的最大键值和
Problem: 1373. 二叉搜索子树的最大键值和 文章目录 思路解题方法复杂度Code 思路 解决这个问题的关键在于采用深度优先搜索(DFS)策略,并结合树形动态规划的思想。我们需要设计一个递归函数,它不仅能够遍历整棵树,还能…...
基于java + Springboot 的二手物品交易平台实现
目录 📚 前言 📑摘要 📑系统架构 📚 数据库设计 📚 系统功能的具体实现 💬 登录模块 首页模块 二手商品轮播图添加 💬 后台功能模块 二手商品商品列表 添加二手商品商品 添加购物车 &a…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
