算法通关村第十六关-白银挑战滑动窗口经典题目

大家好我是苏麟 , 今天带来滑动窗口经典的一些题目 .

我们继续来研究一些热门的、高频的滑动窗口问题

大纲

    • 最长子串专题
      • 无重复字符的最长子串
    • 长度最小的子数组
    • 盛最多水的容器

最长子串专题

无重复字符的最长子串

描述 :

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

题目 :

LeetCode 3. 无重复字符的最长子串 :

无重复字符的最长子串

分析 :

官方题解

解析 :

class Solution {public int lengthOfLongestSubstring(String s) {if(s == null || s.length() == 0){return 0;}HashMap<Character,Integer> map = new HashMap<>();int left = 0;int max = 0;for(int right = 0;right < s.length();right++){if(map.containsKey(s.charAt(right))){left = Math.max(left,map.get(s.charAt(right)) + 1);}map.put(s.charAt(right),right);max = Math.max(max,right - left + 1);}return max;}
}

长度最小的子数组

描述 :

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

题目 :

LeetCode 209. 长度最小的子数组 :

长度最小的子数组

在这里插入图片描述

分析 :

这题直接用双指针就完事了 , 没什么好说的 .

当然用队列啊 也是可以的 .

解析 :

class Solution {public int minSubArrayLen(int target, int[] nums) {int length = nums.length - 1;int left = 0;int right = 0;int res = 0;int min = Integer.MAX_VALUE;while(right <= length){res += nums[right++];while(res >= target){res -= nums[left++];min = Math.min(min, right - left + 1);}}return min == Integer.MAX_VALUE ? 0 : min;}
}

盛最多水的容器

描述 :

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i])

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

题目 :

LeetCode 11. 盛最多水的容器 :

盛最多水的容器
在这里插入图片描述

分析 :

本题看似复杂,但其实简单的很。设两指针i,j,指向的水槽板高度分别为 h[i],h[j],此状态下水槽面积为S(i,j)。由于可容纳水的高度由两板中的 短板 决定,因此可得如下面积公式:

s(i,j)=min(h[i],h[j]) x ( j - i )

在每个状态下,无论长板或短板向中间收窄一格,都会导致水槽底边宽度-1 变短:

  • 若向内移动短板,水槽的短板min(h[i],h[j]) 可能变大,因此下个水槽的面积可能增大
  • 若向内移动长板,水槽的短板min(h[i],h[j]) 不变或变小,因此下个水槽的面积一定变小。

因此,只要初始化双指针分列水槽左右两端,循环每轮将短板向内移动一格,并更新面积最大值,直到两指针相遇时跳出;即可获得最大面积。

解析 :

class Solution {public int maxArea(int[] height) {if(height.length < 2){return 0;}int res = 0;int left = 0;int right = height.length - 1;while(left < right){res = height[left] < height[right] ?Math.max(res,(right - left) * height[left++]) :Math.max(res,(right - left) * height[right--]);} return res;}
}

这期就到这里 , 下期见!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/209385.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

贸易公司ERP用什么软件好

不同行业的贸易公司有不同的业务结构和管理模式&#xff0c;日常经营管理过程中遇到的难点呈现多样化&#xff0c;而很多贸易公司在仓库、财务、销售、采购、订单、客户等业务一体化和部门协同效率等方面还有很多提升空间。 有些贸易公司涉及多仓库、多门店、多税制、多汇率、…

如何绕过某讯手游保护系统并从内存中获取Unity3D引擎的Dll文件

​ 某讯的手游保护系统用的都是一套&#xff0c;在其官宣的手游加固功能中有一项宣传是对比较热门的Unity3d引擎的手游保护方案&#xff0c;其中对Dll文件的保护介绍如下&#xff0c; “Dll加固混淆针对Unity游戏&#xff0c;对Dll模块的变量名、函数名、类名进行加密混淆处理&…

CSS实现小球边界碰撞回弹

如何通过CSS实现一个物体在屏幕中无限的边界碰撞回弹呢&#xff1f;我们可以使用动画效果实现 代码 我们只做一个小球&#xff0c;通过定位属性叠加动画的方式&#xff0c; 让小球在屏幕中进行运动&#xff0c;通过设置animation的alternate属性来设置回弹。最后&#xff0c;只…

笔记-基于CH579M模块通过网线直连电脑进行数据收发(无需网络)

刚学习&#xff0c;做个记录。 基于CH579M模块通过网线直连电脑进行数据收发(无需网络) 目录 一、工具1、CH579模块2、 网线3、电脑以及网络调试工具 二、操作步骤1、TCP/UDP等程序下载以及设置以太网IP2、网络断开3、检查以太网是否正常显示并稳定4、打开网络调试助手进行测试…

电气间隙和爬电距离的算法

电气间隙和爬电距离 一、定义 1、电气间隙&#xff1a;不同电位的两个导电部件间最短的空间直线距离。 2、爬电距离&#xff1a;不同电位的两个导电部件之间沿绝缘材料表面的最短距离。 3、隔离距离&#xff08;机械式开关电器一个极的&#xff09;&#xff1a;满足对隔离器…

音频处理关键知识点

1 引言 现实生活中&#xff0c;我们听到的声音都是时间连续的&#xff0c;我们称为这种信号叫模拟信号。模拟信号需要进行数字化以后才能在计算机中使用。 目前我们在计算机上进行音频播放都需要依赖于音频文件。音频文件的生成过程是将声音信息采样、量化和编码产生的数字信号…

echarts笔记-GeoJSON河北数据下并裁剪为冀北地图并使用echarts加载

首先找个网站把河北的GeoJSON数据下载下来&#xff0c;我用的是这个&#xff0c;理论上任意一个都可以 DataV.GeoAtlas地理小工具系列 将json数据下载后&#xff0c;进行裁剪&#xff0c;仅保留冀北数据。 如下&#xff0c;我裁剪的数据&#xff1a; {"type": &qu…

Python练习题(四)

本文主要是【Python】——Python练习题的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 &#x1f304;每日一句&#xff1a;狠狠沉淀&a…

ssm医院门诊互联电子病历管理信息系统源码和论文

摘 要 网络的广泛应用给生活带来了十分的便利。所以把医院门诊互联电子病历管理与现在网络相结合&#xff0c;利用java技术建设医院门诊互联电子病历管理信息系统&#xff0c;实现医院门诊互联电子病历的信息化。则对于进一步提高医院门诊互联电子病历管理发展&#xff0c;对…

最强Node js 后端框架学习看这一篇文章就够

距离上次认真花时间写作&#xff0c;似乎已经过了许久许久&#xff0c;前端讲了一个新框架 &#xff0c;叫 Nest.js 下方是课件&#xff0c;有过一定开发经验可跟随视频学习 B站 地址 &#xff1a; https://www.bilibili.com/video/BV1Lg4y197u1/?vd_sourcead427ffaf8a5c8344…

leetcode 202.快乐数

代码&#xff1a; class Solution {//计算 n 每个位置上的数字的平方和public int quadraticSum(int n){int sum0;while (n>0){int in%10;sumi*i;n/10;}return sum;}public boolean isHappy(int n) {//慢指针int slown;//快指针int fastquadraticSum(n);while (slow!fast){…

【EasyExcel实践】万能导出,一个接口导出多张表以及任意字段(可指定字段顺序)

文章目录 前言正文一、POM依赖二、核心Java文件2.1 自定义表头注解 ExcelColumnTitle2.2 自定义标题头的映射接口2.3 自定义有序map存储表内数据2.4 表头工厂2.5 表flag和表头映射枚举2.6 测试用的实体2.6.1 NameAndFactoryDemo2.6.2 StudentDemo 2.7 启动类2.8 测试控制器 三、…

linux作业管理_jobs

4.2 作业管理 是指控制当前正在运行的进程的行为&#xff0c;也称为进程控制。 是shell的一个特性&#xff0c;使用户能在多个独立进程间进行切换。 例如&#xff0c;用户可以挂起一个正在运行的进程&#xff0c;稍后再恢复其运行。当用户使用vim编辑一个文本文件&#xff0c…

PCL 空间直角坐标系与极坐标系的相互转换(C++详细过程版)

目录 一、算法原理1、空间坐标系转极坐标系2、极坐标系转空间坐标系二、代码实现三、结果展示1、空间坐标系转极坐标系2、极坐标系转空间坐标系本文由CSDN点云侠原创,原文链接。爬虫网站自重。如果你不是在点云侠的博客中看到该文章,那么此处便是不

【算法】单调栈题单(矩阵系列、字典序最小、贡献法)⭐

文章目录 题单来源经典题单496. 下一个更大元素 I&#xff08;单调栈模板题&#xff09;503. 下一个更大元素 II&#xff08;单调栈循环数组&#xff09;2454. 下一个更大元素 IV&#xff08;第二个更大的元素&#xff1a;两个单调栈&#xff09;456. 132 模式&#xff08;单调…

C++ day44完全背包问题 零钱兑换Ⅱ 组合总和Ⅳ

完全背包&#xff1a;一个物品可以使用无数次&#xff0c;将01背包中倒序遍历背包变成正序遍历背包 遍历顺序&#xff1a;在完全背包中&#xff0c;对于一维dp数组来说&#xff0c;其实两个for循环嵌套顺序是无所谓的&#xff01; 先遍历物品&#xff0c;后遍历背包可以&#…

idea报错——Access denied for user ‘root‘@‘localhost‘ (using password: YES)

项目场景&#xff1a; 使用idea启动SpringBoot项目报错&#xff0c;可以根据提示看到是数据库的原因&#xff0c;显示使用了密码&#xff0c;具体报错信息如下&#xff1a; 解决方案&#xff1a; 第一步&#xff1a;先去配置文件里面查看连接MySQL的url是否正确&#xff0c;如果…

【蓝桥杯选拔赛真题73】Scratch烟花特效 少儿编程scratch图形化编程 蓝桥杯创意编程选拔赛真题解析

目录 scratch烟花特效 一、题目要求 编程实现 二、案例分析 1、角色分析

JDK1.8_X64在LINUX下安装

JDK1.8在LINUX下安装步骤&#xff1a; 在/usr/lib/目录下新建jvm文件夹&#xff0c;如果已有jvm文件夹&#xff0c;则将之前的JDK版本删除&#xff0c;即在jvm目录下执行命令&#xff1a;rm–rf *将JDK文件jdk-8u40-linux-x64.gz拷贝到/home/目录下&#xff1b;在/home/目录下…

华天动力-OA8000 MyHttpServlet 文件上传漏洞复现

0x01 产品简介 华天动力OA是一款将先进的管理思想、 管理模式和软件技术、网络技术相结合,为用户提供了低成本、 高效能的协同办公和管理平台。 0x02 漏洞概述 华天动力OA MyHttpServlet 存在任意文件上传漏洞,未经身份认证的攻击者可上传恶意的raq文件并执行raq文件中的任意…