【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…...

(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...

【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...

MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解
文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...

JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...