滑动窗口练习(二)— 子数组中满足max -min <= sum的个数
题目
给定一个整型数组arr,和一个整数num
某个arr中的子数组sub,如果想达标,必须满足:
sub中最大值 – sub中最小值 <= num,
返回arr中达标子数组的数量
暴力对数器
暴力对数器方法主要是用来和另一个方法互相校验正确性,所以不用考虑时间复杂度。
因为要求的是子数组中的最大值和子数组中的最小值相减 <= num。所以整体思路是这样:
求数组 0 ~ N - 1范围内,所有子数组,找到子数组中最小值,看相减后是否达标,如果达标,则count++进行计数。最后return count。
所有子数组挨个枚举,就是 0~ 0范围内子数组,0 ~ 1范围内子数组 0 ~ N - 1范围内子数组。
1 ~ 1范围内子数组,1 ~ 2 范围内子数组 1 ~ N - 1范围内子数组…。
每个范围内子数组进行枚举,需要两层for循环,找到每个子数组范围内的最大值和最小值,额外需要1层for循环,所以时间复杂度是 O ( N 3 ) O(N^3) O(N3)。
代码
public static int right(int[] arr, int sum) {if (arr == null || arr.length == 0 || sum < 0) {return 0;}int N = arr.length;int count = 0;for (int L = 0; L < N; L++) {for (int R = L; R < N; R++) {int max = arr[L];int min = arr[L];for (int i = L + 1; i <= R; i++) {min = Math.min(min, arr[i]);max = Math.max(max, arr[i]);}if (max - min <= sum) {count++;}}}return count;}
滑动窗口算法
采用滑动窗口算法的时间复杂度是 O ( N ) O(N) O(N),因为窗口不可回退,所以只需要一次遍历即可找出所有符合条件的子数组。
这道题中需要2个窗口,一个维护L…R范围内的最大值,一个维护L…R范围内的最小值。而在看代码之前,需要达成这样的2个共识:
- 如果L…R范围内 max - min <= num,那么L…R范围内所有子数组都满足 max - min <= num,都会达标。
- 如果L…R范围内 max - min > num,那么无论R继续向右扩窗口或者L继续向左阔窗口,那L…R范围内子数组依然不达标。
解释1:
因为max - min <= num,所以L…R 范围内剩余子数组相减,子数组范围内的两个数一定是 < max && > min的,最大值变小了,最小值变大了,所以一定会<= num。
解释2:
因为max - min > num,根据滑动窗口的特性,在维护L…R范围内最大值的双端队列中,后进来的数一定是>=当前双端队列中的值才会进行替换,在维护L…R范围内最小值的双端队列中,后进来的数一定是<=当前双端队列中的值才会进行替换。 所以无论向右或者向左,范围内子数组一定依然不达标。
达成这两个共识之后,代码就简单了很多,在维护双端队列特性的同时,如果满足 max - min <= num,则R向右移,直到不满足 max - min <= num为止。碰见一次不满足,则计算一次当前子数组的个数,直到循环完成。
代码
public static int num(int[] arr, int sum) {if (arr == null || arr.length == 0 || sum < 0) {return 0;}LinkedList<Integer> minWindow = new LinkedList<>();LinkedList<Integer> maxWindow = new LinkedList<>();int R = 0;int count = 0;int N = arr.length;for (int L = 0; L < N; L++) {while (R < N) {//如果max双端队列不为null,并且队列尾端值<=当前值,则弹出while (!maxWindow.isEmpty() && arr[maxWindow.peekLast()] <= arr[R]) {maxWindow.pollLast();}maxWindow.addLast(R);//如果min双端队列不为null,并且队列尾端值>=当前值,则弹出while (!minWindow.isEmpty() && arr[minWindow.peekLast()] >= arr[R]) {minWindow.pollLast();}minWindow.addLast(R);//如果满足条件,则R一直++, 直到不满足条件为止if (arr[maxWindow.peekFirst()] - arr[minWindow.peekFirst()] <= sum) {R++;} else {break;}}//看R - L范围内共有多少个子数组count += R - L;//因为这两个判断走完L就要进行++//所以需要判断当前双端队列中头部值是否要过期了if (maxWindow.peekFirst() == L) {maxWindow.pollFirst();}if (minWindow.peekFirst() == L) {minWindow.pollFirst();}}return count;}
测试
随机生成数组和sum,采用大数据样本量进行测试,用上面两个方法来相互验证。
public static int[] generateRandomArray(int maxLength, int maxValue) {int[] arr = new int[(int) ((maxLength + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random());}return arr;}public static void main(String[] args) {int maxLength = 40;int maxValue = 10000;int sum = 10000;int testNum = 1000000;System.out.println("测试开始");for (int i = 0; i < testNum; i++) {int[] arr = generateRandomArray(maxLength, maxValue);sum = (int) ((sum + 1) * Math.random());int ans1 = right(arr, sum);int ans2 = num(arr, sum);if (ans1 != ans2) {for (int num : arr) {System.out.print(num + " ");}System.out.println();System.out.println("sum : " + sum);System.out.println("ans1 : " + ans1);System.out.println("ans2 : " + ans2);System.out.println("Oops!!");break;}}System.out.println("测试结束");}
相关文章:
滑动窗口练习(二)— 子数组中满足max -min <= sum的个数
题目 给定一个整型数组arr,和一个整数num 某个arr中的子数组sub,如果想达标,必须满足: sub中最大值 – sub中最小值 < num, 返回arr中达标子数组的数量 暴力对数器 暴力对数器方法主要是用来和另一个方法互相校验正…...
用xlwings新建一个excel并同时生成多个sheet
新建一个excel并同时生成多个sheet,要实现如下效果: 一般要使用数据透视表来快速实现。 今天记录用xlwings新建一个excel并同时生成多个sheet。 import xlwings as xw # 打开excel,参数visible表示处理过程是否可视,add_book表示是否打开新的Excel程序…...
诺威信,浪潮云,微众区块链
目录 诺威信B隐私计算平台 浪潮云=星火连-澳优码 HyperChain 产品介绍 CA认证即电子认证服务...
Redux在React中的使用
Redux在React中的使用 1.构建方式 采用reduxjs/toolkitreact-redux的方式 安装方式 npm install reduxjs/toolkit react-redux2.使用 ①创建目录 创建store文件夹,然后创建index和对应的模块,如上图所示 ②编写counterStore.js 文章以counterStore…...
Go 数字类型
一、数字类型 1、Golang 数据类型介绍 Go 语言中数据类型分为:基本数据类型和复合数据类型基本数据类型有: 整型、浮点型、布尔型、字符串复合数据类型有: 数组、切片、结构体、函数、map、通道(channel)、接口 2、…...
时间序列预测 — Informer实现多变量负荷预测(PyTorch)
目录 1 实验数据集 2 如何运行自己的数据集 3 报错分析 1 实验数据集 实验数据集采用数据集4:2016年电工数学建模竞赛负荷预测数据集(下载链接),数据集包含日期、最高温度℃ 、最低温度℃、平均温度℃ 、相对湿度(平均) 、降雨…...
2023年金融信创行业研究报告
第一章 行业概况 1.1 定义 金融信创是指在金融行业中应用的信息技术,特别是那些涉及到金融IT基础设施、基础软件、应用软件和信息安全等方面的技术和产品。这一概念源于更广泛的“信创 (信息技术应用创新)”,即通过中国国产信息技术替换海外信息技术&a…...
51单片机按键控制LED灯亮灭的N个玩法
51单片机按键控制LED灯亮灭的N个玩法 1.概述 这篇文章介绍按键的使用,以及通过控制LED灯的小实验,发现按键中存在的问题,然后思考并解决这些问题。达到熟练使用按键控制元器件。 2.搭建硬件环境 1.硬件准备 名称型号数量单片机STC12C205…...
推荐6款本周 yyds 的开源项目
🔥🔥🔥本周GitHub项目圈选: 主要包含 链接管理、视频总结、有道音色情感合成、中文文本格式校正、GPT爬虫、深度学习推理 等热点项目。 1、Dub 一个开源的链接管理工具,可自定义域名将繁杂的长链接生成短链接,便于保…...
【Git】git 更换远程仓库地址三种方法总结分享
因为公司更改了 gitlab 的网段地址,发现全部项目都需要重新更改远程仓库的地址了,所以做了个记录,说不定以后还会用到呢。 一、不删除远程仓库修改(最方便) # 查看远端地址 git remote -v # 查看远端仓库名 git rem…...
springboot 返回problem+json
spring所有配置都在WebMvcAutoConfiguration中 其中有 ProblemDetailsExceptionHandler 容器中的一个组件 -ControllerAdvice用来集中处理异常的 -点进ResponseEntityExceptionHandler 包含这些异常,如果出现以下异常,会被springboot支持以RFC 7807规…...
AI动画制作 StableDiffusion
1.brew -v 2.安装爬虫项目包所必需的python和git等系列系统支持部件 brew install cmake protobuf rust python@3.10 git wget pod --version brew link --overwrite cocoapods 3.从github网站克隆stable-diffusion-webui爬虫项目包至本地 ssh-add /Users/haijunyan/.ssh/id_r…...
【开源】基于Vue和SpringBoot的木马文件检测系统
项目编号: S 041 ,文末获取源码。 \color{red}{项目编号:S041,文末获取源码。} 项目编号:S041,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 木马分类模块2.3 木…...
5 动态规划解分割等和子串
来源:LeetCode第416题 难度:中等 描述:给你一个只包含正整数的非空数组nums,请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等 分析:相当于从nums数组中选取一些元素,使得他们的和为…...
file_get_contents() 函数详解与使用
概述 在PHP中,file_get_contents() 函数是一个强大的工具,它既可以用于读取本地文件的内容,也可以用于发起 HTTP 请求获取远程资源。本文将详细介绍 file_get_contents() 函数的两种主要用途,并探讨如何充分利用这个函数。 1. 文…...
某医生用 ChatGPT 在 4 个月内狂写 16 篇论文,其中 5 篇已发表,揭密ChatGPT进行论文润色与改写的秘籍
如果写过学术论文,想必会有这样的感受: 绞尽脑汁、茶饭不思、夜不能寐、废寝忘食、夜以继日,赶出一篇论文,然后还被导师点评,“写得就是一坨!” 可是,却有人4个月产出了16篇论文,成功…...
进程等待讲解
今日为大家分享有关进程等待的知识!希望读完本文,大家能有一定的收获! 正文开始! 进程等待的引进 既然我们今天要讲进程等待这个概念!那么只有我们把下面这三个方面搞明白,才能真正的了解进程等待&#x…...
MySQL Binlog深度解析:进阶应用与实战技巧【进阶应用】
🎏:你只管努力,剩下的交给时间 🏠 :小破站 MySQL Binlog深度解析:进阶应用与实战技巧 前言第一:Binlog事件详解第二:关于GTIDGTID的结构:GTID的作用:GTID的事…...
openpnp - 给底部相机加防尘罩
文章目录 openpnp - 给底部相机加防尘罩概述笔记END openpnp - 给底部相机加防尘罩 概述 设备标定完, 看着底部相机, 有点担心掉进去东西, 万一从吸嘴掉下去的料(或者清理设备台面时, 不小心掉进去东西)将顶部相机搞短路怎么办. 就想加个防尘罩, 如果有东西掉进去, 可以掉到机…...
mac mysql连接中断重新启动办法
遇到如图所示问题,可以用下面的命令重启mysql服务 sudo /usr/local/mysql/support-files/mysql.server start...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
