Leetcode - 滑动窗口
文章目录
- 1. 滑动窗口
- 2. 举例
- 2.1 无重复字符的最长子串
- 2.2 长度最小的子数组
- 2.3 滑动窗口最大值
- 2.4 最小覆盖子串
- 2.5 删除有序数组中的重复项
1. 滑动窗口
- 滑动窗口的大概思想如下:
- 可以通过两个指针来标识窗口的边界。
- 窗口的长度是可以固定的,也可以是可变的,完全取决于求解的问题性质。
- 维护一个或者一组和窗口相关联的状态变量,能有效降低计算量和算法复杂度。
- 算法思想:什么是滑动窗口?
其实就是一个队列,比如例题中的
abcabcbb
,进入这个队列(窗口)为ab
c 满足题目要求,当再进入a
,队列变成了abca
,这时候不满足要求。所以,我们要移动这个队列
如何移动?我们只要把队列的左边的元素移出就行了,直到满足题目要求
2. 举例
下面例子采用语言
JAVA
2.1 无重复字符的最长子串
无重复字符的最长子串
class Solution {public int lengthOfLongestSubstring(String s) {int[] last = new int[128];for(int i = 0; i < 128; i++) {last[i] = -1;}int res = 0;int start = 0; // 窗口开始位置int n = s.length();for(int i = 0; i < s.length(); i++) {int index = s.charAt(i);start = Math.max(start, last[index]);//last[index]代表上一次出现的位置,但是字符串内字符不能重复,所以要从上一次出现位置的下一个位置开始//last[index]的存在是为了使得窗口滑动到下一个位置res = Math.max(res, i - start + 1);//当前字符串个数 = 数据末指针-窗口初始位置+1last[index] = i+1;//窗口的下一个位置赋值}return res;}
}
2.2 长度最小的子数组
长度最小的子数组 && 参考文档
class Solution {public int minSubArrayLen(int target, int[] nums) {int i=0,j=0,sum=0,min = Integer.MAX_VALUE;while(i<nums.length){sum = sum +nums[i++];while(sum >= target){min = Math.min(min,i-j);sum = sum - nums[j++];}}return min == Integer.MAX_VALUE ? 0 : min;}
}
2.3 滑动窗口最大值
滑动窗口最大值
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int length = nums.length;int i = 0,j = 0;int out = length-k+1;//外循环次数 int []arr = new int[out];for(i = 0; i<out ; i++){int max = Integer.MIN_VALUE;for(j = i; j<i+k ; j++){max = Math.max(max,nums[j]);}arr[i] = max;}return arr;}
}
2.4 最小覆盖子串
最小覆盖子串 && 参考文旦
class Solution {public String minWindow(String s, String t) {HashMap<Character,Integer> hs = new HashMap<Character,Integer>();HashMap<Character,Integer> ht = new HashMap<Character,Integer>();for(int i = 0;i < t.length();i ++){ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i), 0) + 1);}String ans = "";int len = 1000000, cnt = 0; for(int i = 0,j = 0;i < s.length();i ++){hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);if(ht.containsKey(s.charAt(i)) && hs.get(s.charAt(i)) <= ht.get(s.charAt(i))) cnt ++;while(j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j)))){int count = hs.get(s.charAt(j)) - 1;hs.put(s.charAt(j), count);j ++;}if(cnt == t.length() && i - j + 1 < len){len = i - j + 1;ans = s.substring(j,i + 1);}}return ans;}
}
2.5 删除有序数组中的重复项
删除有序数组中的重复项
class Solution {public int removeDuplicates(int[] nums) {int n = nums.length;if(n == 0) return 0;int fast = 1, slow = 1;while (fast < n) {if (nums[fast] != nums[fast - 1]) {nums[slow] = nums[fast];slow ++;}fast ++;}return slow;}
}
相关文章:
Leetcode - 滑动窗口
文章目录 1. 滑动窗口2. 举例2.1 无重复字符的最长子串2.2 长度最小的子数组2.3 滑动窗口最大值2.4 最小覆盖子串2.5 删除有序数组中的重复项 1. 滑动窗口 滑动窗口的大概思想如下: 可以通过两个指针来标识窗口的边界。窗口的长度是可以固定的,也可以是…...
如何保证数据传输的安全?
要确保数据传输的安全,您可以采取以下措施: 使用加密协议:使用安全的传输协议,如HTTPS(HTTP over SSL/TLS)或其他安全协议,以保护数据在传输过程中的安全性。加密协议可以有效防止数据被窃听或篡改。 强化身份验证&…...
政务、商务数据资源有效共享:让数据上“链”,记录每一个存储过程!
数据上链是目前“区块链”最常见的场景。因为链上所有参与方都分享了统一的事实来源,所有人都可以即时获得最新的信息,数据可用不可见。因此,不同参与方之间的协作效率得以大幅提高。同时,因为区块链上的数据难以篡改,…...
xml转map工具类
背景:最近遇到接口返回是xml,所以需要整一个转换的工具类,方便后续其他xml处理。 依赖引入: <dependency><groupId>dom4j</groupId><artifactId>dom4j</artifactId><version>1.1</versi…...
C++并发多线程--std::future_status、std::shared_future和std::atomic的使用
1--std::future_status的使用 std::future_status成员函数含有三种状态:timeout(执行超时)、ready(执行完毕)和deferred(延迟执行),其中 deferred 状态需要用 std::launch::deferred…...
Redis在Java中的基本使用
本片将介绍 Redis 在 Java 中的基本使用 文章目录 1、使用jedis操作redis1.1、Jedis简介1.2、引入jedis的Maven依赖1.2、获取连接1.3、使用实例 2、对于JedisPooled的使用2.1、使用JedisPooled2.2、关于连接池 3、SpringBoot下使用Redis3.1、引入Maven依赖3.2、配置Redis连接3.…...
4.2 C++ Boost 内存池管理库
Boost 库是一个由C/C语言的开发者创建并更新维护的开源类库,其提供了许多功能强大的程序库和工具,用于开发高质量、可移植、高效的C应用程序。Boost库可以作为标准C库的后备,通常被称为准标准库,是C标准化进程的重要开发引擎之一。…...
Django模型基础
文章目录 一、models字段类型概述属性命名限制使用方式逻辑删除和物理删除常用字段类型 二、常用字段参数常用字段选项(通过字段选项,可以实现对字段的约束) 实践创建模型执行迁移命令 并 创建超级用户登录admin后台添加文件和图片字段定义模型字段和约束及在Admin后…...
导读-Linux简介
Linux简介 总所周知,计算机系统包含硬件和软件两部分。硬件部分被称为裸机,主要包括中央处理器(CPU)、内存、外存和各种外部设备。软件部分主要包括系统软件和应用软件两部分。系统软件包括操作系统、汇编语言、编译程序、数据…...
判断平面中两射线是否相交的高效方法
1. 简介 最近在工作中遇到判断平面内两射线是否相交的问题。 对于这个问题的解决,常规的方法是将两条射线拓展为直线,计算直线的交点,而后判断交点是否在射线上。 这种方法,在思路上较为直观,也易于理解。然后,该方法在计算量上相对较大。对于少量射线间的交点计算尚可…...
基于VUE3+Layui从头搭建通用后台管理系统(前端篇)八:自定义组件封装上
一、本章内容 本章实现一些自定义组件的封装,包括数据字典组件的封装、下拉列表组件封装、复选框单选框组件封装、单选框组件封装、文件上传组件封装、级联选择组件封装、富文本组件封装等。 1. 详细课程地址: 待发布 2. 源码下载地址: 待发布 二、界面预览 ![在这里插入图…...
RabbitMq交换机类型介绍
RabbitMq交换机类型介绍 在RabbitMq中,生产者的消息都是通过交换器来接收,然后再从交换器分发到不同的队列,再由消费者从队列获取消息。这种模式也被成为“发布/订阅”。 分发的过程中交换器类型会影响分发的逻辑。 直连交换机:…...
中国电信秋招攻略,考试内容分析
电信秋招简介 每年的毕业生人数都在逐年递增,逐年递增就意味着竞争会越来越大,最好比别人做更充足的准备。要确定好就业方向以及就业的岗位,要了解各种各样的流程,做好一切自己能做到的准备。而对于有想法进入电信公司工作的人来…...
prompt-engineering-note(面向开发者的ChatGPT提问工程学习笔记)
介绍: ChatGPT Prompt Engineering Learning Notesfor Developers (面向开发者的ChatGPT提问工程学习笔记) 课程简单介绍了语言模型的工作原理,提供了最佳的提示工程实践,并展示了如何将语言模型 API 应用于各种任务的应用程序中。 此外&am…...
2011-2021年数字普惠金融指数Bartik工具变量法(含原始数据和Bartik工具变量法代码)
2011-2021年数字普惠金融指数Bartik工具变量法(含原始数据和Bartik工具变量法代码) 1、时间:2011-2020(省级、城市),2014-2020(区县) 2、原始数据来源:北大金融研究中心…...
[ MySQL ] — 常见函数的使用
目录 日期函数 current_date — 获取当前日期 current_time — 获取当前时间 current_timestamp — 获取当前时间戳 date — 获取参数的日期部分 编辑 date_add — 在日期或时间的基础上进行增加 date_sub — 在日期或时间的基础上进行减少 datediff — 计算两个日期相差…...
Spring AOP实现切入增强的两种方式(execution+annotation)-Demo
pom文件依赖 <!-- AOP切面编程启动环境依赖组 --> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId> </dependency> 1、通过execution表达式实现切入增强 package com…...
人工智能在网络安全中的作用:当前的局限性和未来的可能性
人工智能 (AI) 激发了网络安全行业的想象力,有可能彻底改变安全和 IT 团队处理网络危机、漏洞和勒索软件攻击的方式。 然而,对人工智能的能力和局限性的现实理解至关重要,并且存在许多挑战阻碍人工智能对网络安全产生直接的变革性影响。 在…...
BC99 序列中整数去重
描述 输入n个整数的序列,要求对这个序列进行去重操作。所谓去重,是指对这个序列中每个重复出现的整数,只保留该数第一次出现的位置,删除其余位置。 输入描述 输入包含两行,第一行包含一个正整数n(1 ≤ n…...
[PyTorch][chapter 52][迁移学习]
前言: 迁移学习(Transfer Learning)是一种机器学习方法,它通过将一个领域中的知识和经验迁移到另一个相关领域中,来加速和改进新领域的学习和解决问题的能力。 这里面主要结合前面ResNet18 例子,详细讲解一…...
Ceph如何操作底层对象数据
1.基本原理介绍 1.1 ceph中的对象(object) 在Ceph存储中,一切数据最终都会以对象(Object)的形式存储在硬盘(OSD)上,每个的Object默认大小为4M。 通过rados命令,可以查看一个存储池中的所有object信息,例如…...
sklearn机器学习库(二)sklearn中的随机森林
sklearn机器学习库(二)sklearn中的随机森林 集成算法会考虑多个评估器的建模结果,汇总之后得到一个综合的结果,以此来获取比单个模型更好的回归或分类表现。 多个模型集成成为的模型叫做集成评估器(ensemble estimator)…...
FlutterBoost 实现Flutter页面内嵌iOS view
在使用Flutter混合开发中会遇到一些原生比Flutter优秀的控件,不想使用Flutter的控件,想在Flutter中使用原生控件。这时就会用到 Flutter页面中内嵌 原生view,这里简单介绍一个 内嵌 iOS 的view。 注:这里使用了 FlutterBoost。网…...
走嵌入式还是纯软件?学长告诉你怎么选
最近有不少理工科的本科生问我,未来是走嵌入式还是纯软件好,究竟什么样的同学适合学习嵌入式呢?在这里我整合一下给他们的回答,根据自己的经验提供一些建议。 嵌入式领域也可以分为单片机方向、Linux方向和安卓方向。如果你的专业…...
【云计算原理及实战】初识云计算
该学习笔记取自《云计算原理及实战》一书,关于具体描述可以查阅原本书籍。 云计算被视为“革命性的计算模型”,因为它通过互联网自由流通使超级计算能力成为可能。 2006年8月,在圣何塞举办的SES(捜索引擎战略)大会上&a…...
Open3D (C++) 基于拟合高差的点云地面点提取
目录 一、算法原理1、原理概述2、参考文献二、代码实现三、结果展示1、原始点云2、提取结果四、相关链接系列文章(连载中。。。): Open3D (C++) 基于高程的点云地面点提取Open3D (C++) 基于拟合平面的点云地面点提取Open3D (C++) 基于拟合高差的点云地面点提取</...
认识Transformer:入门知识
视频链接: https://www.youtube.com/watch?vugWDIIOHtPA&listPLJV_el3uVTsOK_ZK5L0Iv_EQoL1JefRL4&index60 文章目录 Self-Attention layerMulti-head self-attentionPositional encodingSeq2Seq with AttentionTransformerUniversal Transformer Seq2Seq …...
《TCP IP网络编程》第二十四章
第 24 章 制作 HTTP 服务器端 24.1 HTTP 概要 本章将编写 HTTP(HyperText Transfer Protocol,超文本传输协议)服务器端,即 Web 服务器端。 理解 Web 服务器端: web服务器端就是要基于 HTTP 协议,将网页对…...
【AI】文心一言的使用
一、获得内测资格: 1、点击网页链接申请:https://yiyan.baidu.com/ 2、点击加入体验,等待通过 二、获得AI伙伴内测名额 1、收到短信通知,点击链接 网页Link:https://chat.baidu.com/page/launch.html?fa&sourc…...
CSAPP Lab2:Bomb Lab
说明 6关卡,每个关卡需要输入相应的内容,通过逆向工程来获取对应关卡的通过条件 准备工作 环境 需要用到gdb调试器 apt-get install gdb系统: Ubuntu 22.04 本实验会用到的gdb调试器的指令如下 r或者 run或者run filename 运行程序,run filename就…...
Java中使用流将两个集合根据某个字段进行过滤去重?
Java中使用流将两个集合根据某个字段进行过滤去重? 在Java中,您可以使用流(Stream)来过滤和去重两个集合。下面是一个示例代码,展示如何根据对象的某个字段进行过滤和去重操作: import java.util.ArrayList; import java.util.List; impor…...
自动驾驶HMI产品技术方案
版本变更 序号 日期 变更内容 编制人 审核人 文档版本 1 2 1....
Git判断本地是否最新
场景需求 需要判断是否有新内容更新,确定有更新之后执行pull操作,然后pull成功之后再将新内容进行复制到其他地方 pgit log -1 --prettyformat:"%H" HEAD -- . "origin/HEAD" rgit rev-parse origin/HEAD if [[ $p $r ]];thenecho "Is La…...
Spring 整合RabbitMQ,笔记整理
1.创建生产者工程 spring-rabbitmq-producer 2.pom.xml添加依赖 <dependencies><dependency><groupId>org.springframework</groupId><artifactId>spring-context</artifactId><version>5.1.7.RELEASE</version></dep…...
Lua 语言笔记(一)
1. 变量命名规范 弱类型语言(动态类型语言),定义变量的时候,不需要类型修饰 而且,变量类型可以随时改变每行代码结束的时候,要不要分号都可以变量名 由数字,字母下划线组成,不能以数字开头,也不…...
【Redis】什么是缓存穿透,如何预防缓存穿透?
【Redis】什么是缓存穿透,如何预防缓存穿透? 缓存穿透是指查询一个一定不存在的数据,由于缓存中不存在,这时会去数据库查询查不到数据则不写入缓存,这将导致这个不存在的数据每次请求都要到数据库去查询,这…...
LeetCode128.最长连续序列
我这个方法有点投机取巧了,题目说时间复杂度最多O(n),而我调用了Arrays.sort()方法,他的时间复杂度是n*log(n),但是AC了,这样的话这道题还是非常简单的,创建一个Hashmap,以nums数组的元素作为ke…...
Datawhale Django入门组队学习Task02
Task02 首先启动虚拟环境(复习一下之前的) 先退出conda的, conda deactivate然后cd到我的venv下面 ,然后cd 到 scripts,再 activate (powershell里面) 创建admin管理员 首先cd到项目路径下&a…...
PCTA 认证考试高分通过经验分享
作者: msx-yzu 原文来源: https://tidb.net/blog/0b343c9f 序言 我在2023年8月10日,参加了 PingCAP 认证 TiDB 数据库专员 V6 考试 ,并以 90分 的成绩通过考试。 考试总分是100分,超过60分就算通过考试。试卷…...
[Python]pytorch与C交互
文章目录 C库ctypes基础数据类型参数与返回值类型数组指针结构体类型回调函数工具函数 示例 ctypes是Python的外部函数,提供了与C兼容的类型,并允许调用DLL库中的函数。 C库 要使函数能被Python调用,需要编译为动态库: # -fPIC…...
C语言,静态变量static基础及使用实列
static关键字有多种用途。以下是关于静态变量 (static) 的简要概述: 1.静态局部变量: - 在函数内部定义的静态变量。 - 生命周期:从程序开始执行到程序结束。 - 作用域:仅限于在其被定义的函数中。 - 每次调用该函数…...
2023.8.19-2023.8.XX 周报【人脸3D+虚拟服装方向基础调研-Cycle Diffusion\Diffusion-GAN\】更新中
学习目标 1. 这篇是做diffusion和gan结合的,可以参照一下看看能不能做cyclegan的形式,同时也可以调研一下有没有人follow这篇论文做了类似cyclegan的事情 Diffusion-GAN论文精读https://arxiv.org/abs/2206.02262 2. https://arxiv.org/abs/2212.06…...
微表情识别(Python编程,cnn模型)
1.数据集包括7种类别微表情 anger文件夹,3995张 disgust文件夹, 436张照片 fear文件夹,4097张照片 happy文件夹,7215张照片 neutral文件夹,4965张照片 sad文件夹,4830张照片 surprised文件夹, 3…...
More Effective C++学习笔记(2)
目录 条款5:对定制的"类型转换函数"保持警觉条款6:自增(increment)、自减(decrement)操作符前缀形式与后缀形式的区别条款7:千万不要重载&&,||和,操作符条款8:了解各种不同意义的new和de…...
零售行业供应链管理核心KPI指标(三)
完美订单满足率和退货率 完美订单满足率有三个方面的因素影响:订单按时、足量、无损交货。通常情况下零售企业追求线上订单履行周期慢慢达到行业平均水平,就是交付的速度变快了,这个肯定是一件好事情,趋势越来越好。 同时&#…...
广州华锐互动:奶牛难产原因及救治VR仿真实训系统
奶牛难产是一种常见的疾病,对奶牛的健康和生产造成很大的影响。为了解决这一问题,许多奶牛养殖场开始采用VR仿真技术来培训奶牛兽医,帮助学生更好地理解奶牛养殖的实际过程,提高他们的实践能力的教学方式。 VR技术开发公司广州华锐…...
神经网络基础-神经网络补充概念-62-池化层
概念 池化层(Pooling Layer)是深度学习神经网络中常用的一种层级结构,用于减小输入数据的空间尺寸,从而降低模型的计算复杂度,减少过拟合,并且在一定程度上提取输入数据的重要特征。池化层通常紧跟在卷积层…...
第8章:集成学习
个体与集成 同质:相同的基学习器,实现容易,但是很难保证差异性。异质:不同的基学习器,实现复杂,不同模型之间本来就存在差异性,但是很难直接比较不同模型的输出,需要复杂的配准方法。…...
设计HTML5列表和超链接
在网页中,大部分信息都是列表结构,如菜单栏、图文列表、分类导航、新闻列表、栏目列表等。HTML5定义了一套列表标签,通过列表结构实现对网页信息的合理排版。另外,网页中还包含大量超链接,通过它实现网页、位置的跳转&…...
React Native 环境搭建
本文以 Android 开发环境(MacBook,已安装 JDK、SDK、Android Studio )为基础而进行 React Native 环境搭建,iOS 环境类似,可参考搭建。 1、安装 Homebrew 命令: ruby -e "$(curl -fsSL https://raw…...