当前位置: 首页 > news >正文

【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 &#xff0c;写一个函数来判断 s2 是否包含 s1 的排列。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 换句话说&#xff0c;s1 的排列之一是 s2 的 子串 。 示例 示例 1&#xff1a; 输入&#xff1a;s1 “ab” s2…...

情感分析方法与实践

第1关&#xff1a;情感分析的基本方法 情感分析简介 情感分析&#xff0c;又称意见挖掘、倾向性分析等。简单而言&#xff0c;是对带有情感色彩的主观性文本进行分析、处理、归纳和推理的过程。在日常生活中&#xff0c;情感分析的应用非常普遍&#xff0c;下面列举几种常见的…...

迁移学习——CycleGAN

CycleGAN 1.导入需要的包2.数据加载&#xff08;1&#xff09;to_img 函数&#xff08;2&#xff09;数据加载&#xff08;3&#xff09;图像转换 3.随机读取图像进行预处理&#xff08;1&#xff09;函数参数&#xff08;2&#xff09;数据路径&#xff08;3&#xff09;读取文…...

【软件测试】对于测试中的bug,我们真正了解了吗?

目录 1.软件测试的生命周期 1.1.软件测试阶段流程 1.2.各流程的任务 2.什么是bug 2.1.bug的概念 2.2.怎么描述bug 2.3.bug的级别 2.4.bug的生命周期 1.软件测试的生命周期 在学习bug前&#xff0c;我们先来学习一下软件测试的生命周期&#xff0c;也就是测试人员进行测…...

Packer-Fuzzer一款好用的前端高效安全扫描工具

★★免责声明★★ 文章中涉及的程序(方法)可能带有攻击性&#xff0c;仅供安全研究与学习之用&#xff0c;读者将信息做其他用途&#xff0c;由Ta承担全部法律及连带责任&#xff0c;文章作者不承担任何法律及连带责任。 1、Packer Fuzzer介绍 Packer Fuzzer是一款针对Webpack…...

解决卸载TabX explorer软件后导致系统文件资源管理器无法正常使用问题

最近安装了最新版本的鲁大师&#xff0c;安装过程中不小心同时安装了捆绑软件TabX explorer。这个软件和系统自带的文件资源管理器很像&#xff0c;最后弹出会员到期才发现&#xff0c;这个不是系统文件资源管理器&#xff0c;是第三方的文件资源管理器&#xff0c;就按正常流程…...

qt for android 使用打包sqlite数据库文件方法

1.在使用sqlite数据库时&#xff0c;先将数据库文件打包&#xff0c;放置在assets中如下图: 将文件放置下android中的assets下的所有文件都会打包在APK中&#xff0c;可以用7zip查看apk文件 2.在qt代码读取数据文件&#xff0c;注意在assets下的文件都是Read-Only&#xff0c;需…...

MYBATIS大于等于、小于等于的写法

mybatis使用的是xml格式的文件。使用>和<号的时候&#xff0c;会存在与xml的标签的规范冲突。需要写成如下形式&#xff0c;否则会报错。 第一种写法 原符号 替换符号 < < < <> > > >& &amp; &…...

基于堆叠长短期记忆网络 Stacked LSTM 预测A股股票价格走势

前言 系列专栏:【深度学习&#xff1a;算法项目实战】✨︎ 涉及医疗健康、财经金融、商业零售、食品饮料、运动健身、交通运输、环境科学、社交媒体以及文本和图像处理等诸多领域&#xff0c;讨论了各种复杂的深度神经网络思想&#xff0c;如卷积神经网络、循环神经网络、生成对…...

SpringCloud Alibaba Sentinel基础入门与安装

GitHub地址&#xff1a;https://github.com/alibaba/Sentinel 中文文档&#xff1a;https://sentinelguard.io/zh-cn/docs/introduction.html 下载地址&#xff1a;https://github.com/alibaba/Sentinel/releases Spring Cloud Alibaba 官方说明文档&#xff1a;Spring Clou…...

Arduino IDE下载、安装和配置

文章开始先把我自己网盘里的安装包分享给大家&#xff0c;链接&#xff1a;https://pan.baidu.com/s/1cb2_3m0LnuSKLnWP_YoWPw?pwdwwww 提取码&#xff1a;wwww 里面一个是Arduino IDE的安装包&#xff0c;另一个是即将发布的版本。 第一个安装包打开直接按照我的步骤安装就…...

SOBEL图像边缘检测器的设计

本项目使用FPGA设计出SOBEL图像边缘检测器&#xff0c;通过分析项目在使用过程中的工作原理和相关软硬件设计进行分析详细介绍SOBEL图像边缘检测器的设计。 资料获取可联系wechat 号&#xff1a;comprehensivable 边缘可定义为图像中灰度发生急剧变化的区域边界,它是图像最基本…...

Day35:2734. 执行字串操作后的字典序最小字符串

Leetcode 2734. 执行字串操作后的字典序最小字符串 给你一个仅由小写英文字母组成的字符串 s 。在一步操作中&#xff0c;你可以完成以下行为&#xff1a; 选择 s 的任一非空子字符串&#xff0c;可能是整个字符串&#xff0c;接着将字符串中的每一个字符替换为英文字母表中的前…...

【高考志愿】机械工程

目录 一、专业概述 二、学科特点 三、就业前景 四、机械工程学科排名 五、专业选择建议 高考志愿选择机械工程&#xff0c;这是一个需要深思熟虑的决定&#xff0c;因为它不仅关乎未来的学习和职业发展&#xff0c;更是对自我兴趣和潜能的一次重要考量。 一、专业概述 机…...

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命令及使用场景 前言下面进入正题&#xff1a;ldd命令 前言 博主今天ubuntu编译go项目出来的一个可执行文件&#xff0c;放centos运行发现居然依赖于XXlib库。然后我一下就想到两个系统库版本不一致&#xff0c;重编。换系统&#xff0c;导项目&#xff0c;配环境……...

自费5K,测评安德迈、小米、希喂三款宠物空气净化器谁才是高性价比之王

最近&#xff0c;家里的猫咪掉毛严重&#xff0c;简直成了一个活生生的蒲公英&#xff0c;家中、空气中各处都弥漫着猫浮毛甚至所有衣物都覆盖着一层厚厚的猫毛。令人难以置信的是&#xff0c;有时我甚至在抠出的眼屎中都能发现夹杂着几根猫毛。真的超级困扰了。但其实最空气中…...

1373. 二叉搜索子树的最大键值和

Problem: 1373. 二叉搜索子树的最大键值和 文章目录 思路解题方法复杂度Code 思路 解决这个问题的关键在于采用深度优先搜索&#xff08;DFS&#xff09;策略&#xff0c;并结合树形动态规划的思想。我们需要设计一个递归函数&#xff0c;它不仅能够遍历整棵树&#xff0c;还能…...

基于java + Springboot 的二手物品交易平台实现

目录 &#x1f4da; 前言 &#x1f4d1;摘要 &#x1f4d1;系统架构 &#x1f4da; 数据库设计 &#x1f4da; 系统功能的具体实现 &#x1f4ac; 登录模块 首页模块 二手商品轮播图添加 &#x1f4ac; 后台功能模块 二手商品商品列表 添加二手商品商品 添加购物车 &a…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...