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

leetcode 567. 字符串的排列(滑动窗口-java)

滑动窗口

  • 字符串的排列
    • 滑动窗口
    • 代码演示
    • 进阶优化版
  • 上期经典

字符串的排列

难度 -中等
leetcode567. 字符串的排列

给你两个字符串 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 <= 1e4
s1 和 s2 仅包含小写字母
在这里插入图片描述

滑动窗口

这种题目,是明显的滑动窗口算法,相当给你一个 S 和一个 T,请问你 S 中是否存在一个子串,包含 T 中所有字符且不包含其他字符。
题目要求 t 的排列之一是 s 的一个子串。而子串必须是连续的,所以要求的 s 子串的长度跟 t 长度必须相等。
那么我们有必要把 t 的每个排列都求出来吗?当然不用。如果字符串 a 是 b 的一个排列,那么当且仅当它们两者中的每个字符的个数都必须完全相等。
所以,根据上面两点分析,我们已经能确定这个题目可以使用 滑动窗口 + hash表 来解决。

我们使用一个长度和 t 长度相等的固定窗口大小的滑动窗口,在 s 上面从左向右滑动,判断 s 在滑动窗口内的每个字符出现的个数是否跟 t 每个字符出现次数完全相等。

我们定义 need是对 t 内字符出现的个数的统计,定义 wind是对 s 内字符出现的个数的统计。在窗口每次右移的时候,需要把右边新加入窗口的字符个数在 wind 中加 1,把左边移出窗口的字符的个数减 1。如果 need== wind,那么说明窗口内的子串是 t 的一个排列,返回 True;如果窗口已经把 s遍历完了仍然没有找到满足条件的排列,返回 False。

代码演示

 public boolean checkInclusion(String t, String s) {int n = t.length(), m = s.length();if (n > m) {return false;}HashMap<Character, Integer> need = new HashMap<>();HashMap<Character, Integer> wind = new HashMap<>();for (char c : t.toCharArray()){need.put(c,need.getOrDefault(c,0) + 1);}int left = 0;int right  = 0;int valid = 0;while (right < m){//右指针 向右移动 窗口扩大char c = s.charAt(right);right++;//判断新进来的字符 是否是需要的。if (need.containsKey(c)){wind.put(c,wind.getOrDefault(c,0) + 1);if (wind.get(c).equals(need.get(c))){valid++;}}//判断是否需要缩小窗口。while (right - left >= n){//找到直接返回trueif (valid == need.size()){return true;}//如何缩小窗口char d = s.charAt(left);left++;if (need.containsKey(d)){if (need.get(d).equals(wind.get(d))){valid--;}wind.put(d,wind.get(d) - 1);}}}return false;}

进阶优化版

这道题目中说明只有小写字母,因此我们可以用数组代替hash表,进行优化,数组代替hash表有两个好处,
1.优化了常数时间,数组的时间效率高于hash表,
2.优化了内存,数组更省空间,

代码演示:

  public boolean checkInclusion(String t, String s) {int n = t.length(), m = s.length();if (n > m) {return false;}int[] need = new int[26];int[] wind = new int[26];for (char c : t.toCharArray()){++need[c - 'a'];}int left = 0;int right  = 0;while (right < m){//右指针 向右移动 窗口扩大char c = s.charAt(right);right++;//判断新进来的字符 是否是需要的。if (need[c - 'a'] != 0){++wind[c - 'a'];}//判断是否需要缩小窗口。while (right - left >= n){//找到直接返回trueif (Arrays.equals(wind,need)){return true;}//如何缩小窗口char d = s.charAt(left);left++;if (need[d - 'a'] != 0){--wind[d - 'a'];}}}return false;}

上期经典

leetcode76. 最小覆盖子串

相关文章:

leetcode 567. 字符串的排列(滑动窗口-java)

滑动窗口 字符串的排列滑动窗口代码演示进阶优化版 上期经典 字符串的排列 难度 -中等 leetcode567. 字符串的排列 给你两个字符串 s1 和 s2 &#xff0c;写一个函数来判断 s2 是否包含 s1 的排列。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 换句…...

Git —— 分支重命名操作

在开发中&#xff0c;对某个分支进行重命名的操作&#xff1a; 1、本地分支重命名 本地分支是指&#xff1a;你当前这个分支还没有推送到远程的情况&#xff0c;这种情况修改分支名称就要方便很多 git branch -m 原始名称 新名称 //示例&#xff1a; 修改 test 为 newTest g…...

JavaIO流

JavaIO流 一、概念二、File类三、File类的使用1、File文件/文件夹类的创建2、File类的获取操作3、File类判断操作 - boolean4、File类对文件/文件夹的增删改5、File类的获取子文件夹以及子文件的方法 四、Java中IO流多种维度的维度1、按照流向 - Java程序2、按照流的大小分类3、…...

FlinkSql 如何实现数据去重?

摘要 很多时候flink消费上游kafka的数据是有重复的&#xff0c;因此有时候我们想数据在落盘之前进行去重&#xff0c;这在实际开发中具有广泛的应用场景&#xff0c;此处不说详细代码&#xff0c;只粘贴相应的flinksql 代码 --********************************************…...

机器学习概念

目录 一、人工智能、机器学习、深度学习的关系 二、什么是深度学习&#xff1f; 2.1 深度学习常用算法 一、人工智能、机器学习、深度学习的关系 人工智能、机器学习和深度学习的关系如下所示。 二、什么是深度学习&#xff1f; 深度学习( DL, Deep Learning) 是机器学习 …...

【数据结构】排序(插入、选择、交换、归并) -- 详解

一、排序的概念及其运用 1、排序的概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xff1a;假定在待排序的记录序列中&#xff0c;存在多个具有相同的关键字的记…...

游戏中的图片打包流程,免费的png打包plist工具,一款把若干资源图片拼接为一张大图的免费工具

手机游戏开发中&#xff0c;为了提高图片渲染性能&#xff0c;经常需要将小图片合并成一张大图进行渲染。如果手工来做的话就非常耗时。TexturePacker就是一款非常不错方便的处理工具。TexturePacker虽然非常优秀&#xff0c;但不是免费的。 对于打包流程&#xff0c;做游戏的…...

Springboot实现ENC加密

Springboot实现ENC加密 1、导入依赖2、配置加密秘钥&#xff08;盐&#xff09;3、获取并配置密文4、重启项目测试5、自定义前缀、后缀6、自定义加密方式 1、导入依赖 关于版本&#xff0c;需要根据spring-boot版本&#xff0c;自行修改 <dependency><groupId>co…...

nginx 托管vue项目配置

server {listen 80;server_name your_domain.com;location / {root /path/to/your/vue/project;index index.html;try_files $uri $uri/ /index.html;} }奇怪的现象,在vue路由中/会跳转到/abc/def&#xff0c;但如果直接输入/abc/def会显示404&#xff0c;添加 try_files $uri…...

Vue3中如何进行封装?—组件之间的传值

用了很久一段时间Vue3Ts了&#xff0c;工作中对一些常用的组件也进行了一些封装&#xff0c;这里对封装的一些方法进行一些简单的总结。 1.props传递 首先在主组件进行定义传值 <template><div>这里是主组件<common :first"first"></common&…...

实训笔记8.25

实训笔记8.25 8.25笔记一、Flume数据采集技术1.1 Flume实现数据采集主要借助Flume的组成架构1.2 Flume采集数据的时候&#xff0c;核心是编写Flume的采集脚本xxx.conf1.2.1 脚本文件主要由五部分组成 二、Flume案例实操2.1 采集一个网络端口的数据到控制台2.1.1 分析案例的组件…...

vue自定义监听元素宽高指令

在 main.js 中添加 // 自定义监听元素高度变化指令 const resizerMap new WeakMap() const resizeObserver new ResizeObserver((entries) > {for (const entry of entries) {const handle resizerMap.get(entry.target)if (handle) {handle({width: entry.borderBoxSiz…...

网络爬虫到底是个啥?

网络爬虫到底是个啥&#xff1f; 当涉及到网络爬虫技术时&#xff0c;需要考虑多个方面&#xff0c;从网页获取到最终的数据处理和分析&#xff0c;每个阶段都有不同的算法和策略。以下是这些方面的详细解释&#xff1a; 网页获取&#xff08;Web Crawling&#xff09;&#x…...

前端行级元素和块级元素的基本区别

块级元素和行内元素的基本区别是&#xff0c; 行内元素可以与其他行内元素并排&#xff1b;块级元素独占一行&#xff0c;不能与其他任何元素并列&#xff1b; 下面看一下&#xff1b; <!DOCTYPE html> <html> <head> <meta charset"utf-8"&…...

CentOS 7用二进制安装MySQL5.7

[rootlocalhost ~]# [rootlocalhost ~]# ll 总用量 662116 -rw-------. 1 root root 1401 8月 29 19:29 anaconda-ks.cfg -rw-r--r--. 1 root root 678001736 8月 29 19:44 mysql-5.7.40-linux-glibc2.12-x86_64.tar.gz [rootlocalhost ~]# tar xf mysql-5.7.40-linux-…...

华为加速回归Mate 60发布, 7nm全自研工艺芯片

华为于今天12:08推出“HUAWEI Mate 60 Pro先锋计划”&#xff0c;让部分消费者提前体验。在华为商城看到&#xff0c;华为Mate 60 pro手机已上架&#xff0c;售价6999元&#xff0c;提供雅川青、白沙银、南糯紫、雅丹黑四种配色供选择。 据介绍&#xff0c;华为在卫星通信领域…...

Linux系列讲解 —— 【systemd】下载及编译记录

Ubuntu18.04的init程序合并到了systemd中&#xff0c;本篇文章记录一下systemd的下载和编译。 1. 下载systemd源码 (1) 查看systemd版本号&#xff0c;用来确定需要下载的分支 sunsun-pc:~$ systemd --version systemd 237 PAM AUDIT SELINUX IMA APPARMOR SMACK SYSVINIT UT…...

u-view 的u-calendar 组件设置默认日期后,多次点击后,就不滚动到默认日期的位置

场景&#xff1a;uniapp开发微信小程序 vue2 uview版本&#xff1a;2.0.36 &#xff1b; u-calendar 组件设置默认日期后 我打开弹窗&#xff0c;再关闭弹窗&#xff0c; 重复两次 就不显示默认日期了 在源码中找到这个位置进行打印值&#xff0c;根据出bug前后的值进行…...

vue naive ui 按钮绑定按键

使用vue (naive ui) 绑定Enter 按键 知识点: 按键绑定Button全局挂载使得message,notification, dialog, loadingBar 等NaiveUI 生效UMD方式使用vue 与 naive ui将vue默认的 分隔符大括号 替换 为 [[ ]] <!DOCTYPE html> <html lang"en"> <head>…...

Viobot基本功能使用及介绍

设备拿到手当然是要先试一下效果的&#xff0c;这部分可以参考本专栏的第一篇 Viobot开机指南。 接下来我们就从UI开始熟悉这个产品吧&#xff01; 1.状态 设备上电会自动运行它的程序&#xff0c;开启了一个服务器&#xff0c;上位机通过连接这个服务器连接到设备&#xff0c…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...