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

基础算法之滑动窗口--Java实现(上)--LeetCode题解:长度最小的子数组-无重复字符的子串-最大连续1的个数III-将x减到0的最小操作数

这里是Thembefue

今天讲解算法中较为经典的一个算法 => 滑动窗口

本讲解主要通过题目来讲解以理解算法

讲解分为三部分:题目解析 => 算法讲解 => 编写代码

滑动窗口

在正式进入题目的讲解之前,得先了解一下什么是滑动窗口,以及应该在什么情况下使用。

滑动窗口其实是由"暴力遍历"优化来的,其本质也是双指针,但这个双指针是利用数组等单调性同向移动的,不会倒退,使其像一个窗口一个从左向右滑动。

长度最小的子数组

        题目解析

    

找到一个子数组,使这个子数组的和大于等于给定的目标值,子数组是数组上连续的一段,一定是连续的!

        算法讲解 

本题使用暴力遍历的时间复杂度位O(n*2),所以一定会超时。

所以我们在暴力遍历的基础上进行优化,根据数组的单调性,我们没必要在 left 指针向右移时,让 right 指针重新回来再遍历一次,这样会导致重复遍历,徒增时间。

滑动窗口:这个过程一般都分为四步,进窗口,判断,出窗口,更新结果。

其中更新结果可能在出窗口前,也可能在出窗口后,根据题目意思即可。

我们先维护一个 sum 变量,用于表示当前窗口中所有元素的全部和,当和大于等于 target时,我们便可更新结果,并且让此时应该让left 指向的元素出窗口。

        编写代码 

class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0, right = 0;int sum = 0, len = Integer.MAX_VALUE;while (right < nums.length) {// 进窗口sum += nums[right];// 开始缩小窗口while (sum >= target) {len = Math.min(len, right - left + 1);sum -= nums[left++]; // 出窗口} right++;}return len == Integer.MAX_VALUE ? 0 : len;}
}

无重复字符的最长子串

        题目解析

子串和子数组其实就是一个意思,连续的一段子字符串,且这段字符串不能出现重复的字符,返回其最长子串。

        算法讲解 

本题需要借用一个数据结构来实现,也即是哈希表,哈希表记录某个字符出现的次数。

首先是进窗口操作,也就是把当前字符放入到哈希表,同时更新其出现的次数。

当出现了两次相同的字符时,说明此子串不符合条件。此时 left 指针移动,缩小窗口。

随后更新结果。

 

        编写代码

class Solution {public int lengthOfLongestSubstring(String s) {int[] hash = new int[128];int left = 0, right = 0;int len = 0;while (right < s.length()) {// 进窗口hash[s.charAt(right)]++;while (hash[s.charAt(right)] > 1) {// 出窗口hash[s.charAt(left++)]--;}// 更新数据len = Math.max(len, right - left + 1);right++;}return len;}
}

 最大连续1的个数 III

        题目解析

同样是求符合条件的最长子数组,但其实不用真的修改数组的元素,不然要改回去就麻烦了。

        算法讲解 

我们可以使用一个计数器,来统计此时窗口中0出现的次数,0出现了多少次,就要将其变成1多少次。所以进出窗口的操作大差不差。

但是有一个细节,在出窗口时,0计数器不能直接减小,但 left指向的元素为0时,才能减去,否则 left一直减小,直到 0计数器减小到题目条件时。

 

        编写代码 

class Solution {public int longestOnes(int[] nums, int k) {int zeroCount = 0, ret = 0;int left = 0, right = 0;while (right < nums.length) {// 进窗口if (nums[right++] == 0) zeroCount++;while (zeroCount > k) {if (nums[left++] == 0) zeroCount--; // 出窗口}ret = Math.max(ret, right - left);}return ret;}
}

 将 x 减到 0 的最小操作数

        题目解析

选取数组最左边或者最右边的元素,从 x 中减去该元素,直到将 x 减为0为止,但得返回最小的操作次数。

注意:只能选取最左边或者最右边的元素,选过的元素从数组中删除,不能再使用。

        算法讲解 

这题乍一看好像并不是滑动窗口,因为一下操作左边,一下操作右边,并不能形成连续的一段。

但是看问题的角度有多种,俗话说:正难则反。假设我们现在选取了左边和右边的元素的一个,假设此时这两个数字的和正好等于 x,也就是满足题目的条件。

我们不难发现,除去这两个数字,剩下的元素其实构成了一个子数组,也就是一个窗口,且这个窗口的值等于数组所有元素的总和减去 x。

掌握了这个性质,这题就迎刃而解了。

 

        编写代码 

class Solution {public int minOperations(int[] nums, int x) {int left = 0, right = 0;int ret = -1;int sum = 0;for (int i: nums) sum += i;int target = sum - x, temp = 0;if (target < 0) return -1;while (right < nums.length) {// 进窗口temp += nums[right];// 判断while (temp > target) {temp -= nums[left++]; // 出窗口}if (temp == target) ret = Math.max(ret, right - left + 1);right++;}return ret == -1 ? -1 : nums.length - ret;}
}

好了,以上就是今天内容的全部讲解,如果有不懂的地方,随时私聊😘

我们下半部分见😁

相关文章:

基础算法之滑动窗口--Java实现(上)--LeetCode题解:长度最小的子数组-无重复字符的子串-最大连续1的个数III-将x减到0的最小操作数

这里是Thembefue 今天讲解算法中较为经典的一个算法 > 滑动窗口 本讲解主要通过题目来讲解以理解算法 讲解分为三部分&#xff1a;题目解析 > 算法讲解 > 编写代码 滑动窗口 在正式进入题目的讲解之前&#xff0c;得先了解一下什么是滑动窗口&#xff0c;以及应该在什…...

Linux -- 文件系统(文件在磁盘中的存储)

目录 前言&#xff1a; 了解机械磁盘 初始盘片与磁头 盘片是怎么存数据的呢&#xff1f; 详解盘片 如何访问磁盘中的一个扇区呢&#xff1f; -- CHS 定位法 磁盘的逻辑存储 LBA&#xff08;Logical Block Addressing --- 逻辑块寻址&#xff09; 如何将 LBA 地址转换为…...

微服务(Microservices),服务网格(Service Mesh)以及无服务器运算Serverless简单介绍

文章目录 什么是微服务?一、定义与特点二、优势三、组件与架构四、应用场景五、挑战与解决方案什么是服务网格?一、定义与特点二、核心组件三、主要功能四、实现工具五、应用场景六、优势与挑战什么是Serverless?一、定义与特点二、主要领域三、优势四、应用场景五、挑战三者…...

【AIGC】AI时代的数据安全:使用ChatGPT时的自查要点

博客主页&#xff1a; [小ᶻZ࿆] 本文专栏: AIGC | ChatGPT 文章目录 &#x1f4af;前言&#x1f4af;法律法规背景中华人民共和国保守秘密法中华人民共和国网络安全法中华人民共和国个人信息保护法遵守法律法规的重要性 &#x1f4af;ChatGPT的数据使用特点ChatGPT数据安全…...

什么是区块链桥?

什么是区块链桥&#xff1f; 区块链桥是一种实现资产从一个区块链转移至另一个区块链的工具&#xff0c;它解决了区块链技术中不同网络之间缺乏互操作性的问题。区块链桥通过创建代表另一区块链资产的合成衍生品&#xff0c;使得原本互不兼容的区块链资产能够相互连接和转移。…...

机器学习框架

机器学习框架 机器学习框架是用于开发和部署机器学习模型的软件工具。它们提供了一组API和工具&#xff0c;帮助开发人员在各种计算设备上构建、训练和部署机器学习模型。以下是几个常见的机器学习框架&#xff1a; 1.TensorFlow&#xff1a; TensorFlow是一个开源的人工智能…...

金三银四:20道前端手写面试题

文章目录 一、前言二、题目1. 防抖节流解读 2.一个正则题3. 不使用a标签&#xff0c;如何实现a标签的功能4. 不使用循环API 来删除数组中指定位置的元素&#xff08;如&#xff1a;删除第三位&#xff09; 写越多越好5. 深拷贝解读 6. 手写call bind applycall 解读apply 解读 …...

RAC被修改权限及相关问题

RDBMS &#xff1a; 19.19 修改RAC权限及相关问题 修改RAC权限&#xff0c;参考文档&#xff1a; How to check and fix file permissions on Grid Infrastructure environment (Doc ID 1931142.1) Script to capture and restore file permission in a directory (for eg. O…...

Golang | Leetcode Golang题解之第441题排列硬币

题目&#xff1a; 题解&#xff1a; func arrangeCoins(n int) int {return sort.Search(n, func(k int) bool { k; return k*(k1) > 2*n }) }...

数学建模--什么是数学建模?数学建模应该怎么准备?

前言 这是去年底学数学建模老哥的建模课程笔记&#xff1b;未来本人将陆陆续续的更新数学建模相关的一些基础算法&#xff0c;大家可以持续关注一下&#xff1b;提示&#xff1a;数学建模只有实战才能提升&#xff0c;光学算法没有啥意义&#xff0c;也很难学的很懂。 文章目录…...

Java项目实战II基于Java+Spring Boot+MySQL的智能物流管理系统(源码+数据库+文档)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者 一、前言 随着电商行业的蓬勃发展&#xff0c;物流行业迎来了前所未有的机遇与挑战。面对日益增长的订单量和复…...

【数据分享】2000—2023年我国省市县三级逐月植被覆盖度(FVC)数值(Shp/Excel格式)

之前我们分享过2000—2023年我国250米分辨率逐月植被覆盖度&#xff08;FVC&#xff09;栅格数据&#xff08;可查看之前的文章获悉详情&#xff09;&#xff0c;该数据来源于高吉喜等学者在国家青藏高原科学数据中心平台上分享的数据&#xff0c;合成方式采用月最大值合成&…...

《Linux从小白到高手》理论篇(十一):Linux的系统环境管理

值此国庆佳节&#xff0c;深宅家中&#xff0c;闲来无事&#xff0c;就多写几篇博文。本篇详细深入介绍Linux的系统环境管理。 环境变量 linux系统下&#xff0c;如果你下载并安装了应用程序&#xff0c;很有可能在键入它的名称时出现“command not found”的提示内容。如果每…...

Qt/C++开源控件 自定义雷达控件

使用Qt框架创建一个简单的雷达图&#xff0c;包含动态扫描、目标点生成、刻度和方向标识。代码实现使用C编写&#xff0c;适合用作学习和扩展的基础。 1. 头文件与基本设置 #include "RadarWidget.h" #include <QPainter> #include <QPen> #include &…...

什么是IDE(集成开发环境)?

集成开发环境(IDE)详解 在软件开发的世界中,集成开发环境(IDE,Integrated Development Environment)扮演着至关重要的角色。它是一个综合性的软件应用程序,旨在为软件开发者提供一整套的、易于使用的工具集,以便他们能够更高效地编写、调试、测试和部署代码。简而言之…...

【Linux】用虚拟机配置Ubuntu 24.04.1 LTS环境

目录 1.虚拟机安装Ubuntu系统 2.Ubuntu系统的网络配置 3.特别声明 首先我们先要下载VMware软件&#xff0c;大家自己去下啊&#xff01; 1.虚拟机安装Ubuntu系统 我们进去之后点击创建新的虚拟机&#xff0c;然后选择自定义 接着点下一步 再点下一步 进入这个界面之后&…...

MacOS升级Ruby版本详解:步骤、挑战与解决方案

MacOS升级Ruby版本详解&#xff1a;步骤、挑战与解决方案 在MacOS上升级Ruby版本是一个涉及多个步骤和考虑因素的过程。Ruby作为一种广泛使用的编程语言&#xff0c;其新版本通常会引入一系列改进&#xff0c;包括性能优化、安全修复和新特性。因此&#xff0c;升级Ruby版本不…...

Log4j的配置与使用详解

Log4j的配置与使用详解 Log4j介绍 Log4j是Apache的一个开源项目&#xff0c;通过使用Log4j&#xff0c;我们可以控制日志信息输送的目的地是控制台、文件、GUI组件&#xff0c;我们可以控制每条日志的输出格式&#xff1b;只需要通过一个配置文件就可以灵活的配置&#xff0c…...

docker 的目录有那些,分别存放什么东西

Docker 的目录结构和文件存放位置取决于你所使用的操作系统和Docker的版本。以下是一些常见的目录和它们通常存放的内容&#xff1a; 通用目录 /var/lib/docker (Linux) 这是Docker在Linux系统上的主要数据目录。存放了镜像、容器、数据卷、网络等的元数据和状态信息。具体结构…...

开源模型应用落地-模型微调-语料采集-数据格式化(四)

一、前言 在自然语言处理(NLP)的快速发展中,语料采集作为基础性的步骤显得尤为重要。它不仅为机器学习模型提供了所需的训练数据,还直接影响模型的性能和泛化能力。随着数据驱动技术的不断进步,如何有效并高效地收集、清洗和整理丰富多样的语料,已成为研究者和工程师们亟…...

C语言+单片机

今天内容有点水哈哈&#xff08;忙着练焊铁技术了嘻嘻&#xff09; C语言 简单学习了while语言以及其与for语言的区别和适用方法 .循环结构&#xff1a; 初始化语句条件判断句条件控制句 for语句 for(int1;i<100;i){执行条件} for (int i 1; i < 100; i) {printf(&quo…...

vmvare虚拟机centos 忘记超级管理员密码怎么办?

vmvare虚拟机centos 忘记超级管理员密码怎么办?如何重置密码呢? 一、前置操作 重启vmvare虚拟机的过程中,长按住Shift键 选择第一个的时候,按下按键 e 进入编辑状态。 然后就会进入到类似这个界面中。 在下方界面 添加 init=/bin/sh,然后按下Ctrl+x进行保存退出。 init=/bi…...

使用 Vue3 和 Axios 实现 CRUD 操作

文章目录 1、准备工作2、创建 Vue 3 项目3、项目结构4、实现 CRUD 操作5、运行项目6、小结在当今的前端开发中,Vue.js 作为一款流行的 JavaScript 框架,正在被越来越多的开发者所青睐。尤其是 Vue 3 引入了 Composition API 和更优雅的响应式处理,使得模板编写和状态管理变得…...

.NET MAUI(.NET Multi-platform App UI)下拉选框控件

MAUI下拉选框控件详解&#xff1a; 在开发跨平台应用程序时&#xff0c;下拉选框&#xff08;ComboBox&#xff09;是一个极为常见且实用的控件&#xff0c;它允许用户从一组预定义的选项中选择一个。在.NET MAUI&#xff08;.NET Multi-platform App UI&#xff09;框架中&am…...

C++平台跳跃游戏

目录 开头程序Game.cpp源文件Player.h头文件Player.cpp源文件 程序的流程图程序游玩的效果下一篇博客要说的东西 开头 大家好&#xff0c;我叫这是我58。 程序 Game.cpp源文件 #include <iostream> #include "Player.h" using namespace std; void printma…...

多系统萎缩患者必看!这些维生素助你对抗病魔

亲爱的朋友们&#xff0c;今天我们来聊聊一个相对陌生但重要的健康话题——多系统萎缩&#xff08;MSA&#xff09;。这是一种罕见的神经系统疾病&#xff0c;影响着患者的自主神经系统、运动系统和平衡功能。面对这样的挑战&#xff0c;科学合理的饮食和营养补充显得尤为重要。…...

深度学习模型性能优化实战之从评估到提升的全流程解析

1. 概述 在构建和使用机器学习模型的过程中&#xff0c;模型的效果评估和优化是两个至关重要的环节。无论模型是用于分类、回归还是其他任务&#xff0c;评估其表现以及持续优化模型性能&#xff0c;都是确保模型在实际应用中取得成功的关键。本节将重点介绍模型效果评估的定义…...

C++ | Leetcode C++题解之第446题等差数列划分II-子序列

题目&#xff1a; 题解&#xff1a; class Solution { public:int numberOfArithmeticSlices(vector<int> &nums) {int ans 0;int n nums.size();vector<unordered_map<long long, int>> f(n);for (int i 0; i < n; i) {for (int j 0; j < i;…...

【解密 Kotlin 扩展函数】扩展属性与扩展函数类似(十九)

导读大纲 1.1.1 扩展属性的创建和使用 1.1.1 扩展属性的创建和使用 之前, 我们已经了解声明 Kotlin 属性的语法 Kotlin中的顶级属性–传送门就像扩展函数一样,我们也可以指定扩展属性就像之前所说&#xff0c;属性和函数的区别在于前者是特征&#xff0c;后者是行为 相比扩展函…...

【Spring Boot 入门二】Spring Boot中的配置文件 - 掌控你的应用设置

一、引言 在上一篇文章中&#xff0c;我们开启了Spring Boot的入门之旅&#xff0c;成功构建了第一个Spring Boot应用。我们从环境搭建开始&#xff0c;详细介绍了JDK的安装以及IDE的选择与配置&#xff0c;然后利用Spring Initializr创建了项目&#xff0c;分析了项目结构&am…...

加盟餐饮网站建设/本地广告推广平台哪个好

阿里云轻量应用服务器怎么远程连接&#xff1f;轻量服务器可以更换操作系统吗&#xff1f;使用轻量应用服务器如何搭建网站&#xff1f;轻量应用服务器端口如何开通&#xff1f;阿里云百科来详细说下轻量服务器远程连接、搭建网站、开放端口等详细使用教程&#xff1a; 目录 …...

重庆酉阳网站设计公司/青岛seo服务公司

&#x1f680; 优质资源分享 &#x1f680; 学习路线指引&#xff08;点击解锁&#xff09;知识定位人群定位&#x1f9e1; Python实战微信订餐小程序 &#x1f9e1;进阶级本课程是python flask微信小程序的完美结合&#xff0c;从项目搭建到腾讯云部署上线&#xff0c;打造一…...

wordpress 重定向过多/外贸网站优化推广

公有链 公共链是真正意义上的去中心化分布式区块链&#xff0c;系统安全性 由工作量证明或权益证明机制来保证&#xff0c;容易进行应用程序部 署&#xff0c;全球范围可以访问&#xff0c;不依赖于单个公司或者辖区。公共链参与者往往匿名性强&#xff0c;任何参与者都可以在…...

线上商城如何推广/电脑系统优化软件

1.jmap导出内存映像文件与内存使用情况&#xff1a; 基本语法: 导出内存映像文件&#xff1a; 显示堆内存相关信息&#xff1a; 小结&#xff1a; 2.jhat&#xff08;JDK自带堆分析工具&#xff09;&#xff1a; 基本语法&#xff1a; 3.jstack追踪JVM中线程快照&#xff1…...

公司网站建设进度/营销新闻

java读取txt文件内容。可以作如下理解&#xff1a;首先获得一个文件句柄。File file new File(); file即为文件句柄。两人之间连通电话网络了。接下来可以开始打电话了。通过这条线路读取甲方的信息&#xff1a;new FileInputStream(file) 目前这个信息已经读进来内存当中了。…...

网站目录结构说明/沈阳网站关键词优化多少钱

一 下载验证文件 为了搭建课程环境&#xff0c;首先需要RHCI foundation 和 课程 foundation &#xff0c;文件 如下&#xff1a;The current list of files for the foundation layer:* RHCIfoundation-RHEL71-*.icmf (manifest file)* rhel-server-7.1-x86…...