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

【LeetCode每日一题】525连续数组 303区域和检索(前缀和的基本概念和3个简单案例)

前缀和

在这里插入图片描述

// 构造prefix
let prefix = [0]
arr.forEach(num => {prefix.push(prefix.at(-1) + num);
})

如果想要计算某个区间 i 到 j 这个子数组的和时,可以根据 prefix[j+1] - prefix[i] 获得。

例题1:303.区域和检索 - 数组不可变

给定一个整数数组 nums,处理以下类型的多个查询:

  1. 计算索引 leftright (包含 leftright)之间的 nums 元素的 ,其中 left <= right

实现 NumArray 类:

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 leftright 之间的元素的 总和 ,包含 leftright 两点(也就是 nums[left] + nums[left + 1] + ... + nums[right] )
/*** @param {number[]} nums*/
var NumArray = function(nums) {this.sum = new Array(nums.length+1).fill(0);for(let i =0;i<n;i++){this.sum[i+1] = this.sum[i]+nums[i]}
};/** * @param {number} left * @param {number} right* @return {number}*/
NumArray.prototype.sumRange = function(left, right) {return this.sum[right+1 ]-this.sum[left];
};/*** Your NumArray object will be instantiated and called as such:* var obj = new NumArray(nums)* var param_1 = obj.sumRange(left,right)*/

例题2

数组water表示一排瓶子的水位高度。小明往这些瓶子内浇水,1次操作可以使1个瓶子的水位增加1。给定一个整数cnt,表示小明想通过浇水获得cnt个水位高度一致的瓶子。求最少需要浇水多少次?

比如:[1,2,3,4,100] ,cnt = 4,想要获得4个,最少需要浇水
(4-1) + (4-2)+(4-3)+(4-4)
⇒ 4 * 4 - (1+2+3+4)
⇒ 4* cnt - cnt个元素的区域和。

计算操作次数的公式为:water[i] * cnt - (preSum[i + 1] - preSum[i - cnt + 1])
这个公式表示将当前位置到第cnt个瓶子的水位高度都调整为当前位置的水位高度所需的总操作次数。

下面是修改后的代码实现:

const MinOperations = (water, cnt) => {water.sort((a, b) => b - a); // 按照从大到小排序let preSum = [0];water.forEach((element) => {preSum.push(preSum[preSum.length - 1] + element);});let res = Infinity;for (let i = cnt - 1; i < water.length; i++) {let temp = water[i] * cnt - (preSum[i + 1] - preSum[i - cnt + 1]);if (temp < res) res = temp;if (res === 0) break; // 如果res的值已经为0,表示不需要再进行更多操作,可以跳出循环}return res;
};console.log(MinOperations([7, 1, 9, 10], 3));
console.log(MinOperations([5, 3, 5, 10], 2));

在给定的示例中,第一个输入数组为[7, 1, 9, 10],表示瓶子的水位高度,cnt为3。运行代码后,输出为2,表示最少需要浇水2次才能使3个瓶子的水位高度一致。第二个输入数组为[5, 3, 5, 10],cnt为2。运行代码后,输出为3,表示最少需要浇水3次才能使2个瓶子的水位高度一致。

例题3:525. 连续数组

给定一个二进制数组 nums , 找到含有相同数量的 01 的最长连续子数组,并返回该子数组的长度。

妈的 连题目都没有读懂!本来看成是找到两个连续子数组,两个连续子数组的 0 1 个数分别相同,我说怎么看着如此复杂。

题目转换:

找到一个连续子数组,其中0和1 的数量是一致的,求最大的连续子数组的长度。

解题过程

暴力

遍历所有连续子数组的0和1 的个数,如果相同,则维护这个连续子数组的最大长度。

巧妙的转换:

相同数量的0和1 ⇒ 将 0 → -1 ⇒ 连续子数组和 为 0

如果想要求子数组的元素和 ⇒ 计算数组的前缀和。

prefixSum[i] : [0…i] 的前缀和,元素的累加。

[i…k] 的元素累加和 = prefixSum[k]-prefixSum[i-1]

所以:相同数量的0和1 ⇒ 将 0 → -1 ⇒ 连续子数组和 为 0 ⇒ prefixSum[k]-prefixSum[i] = 0 长度为 i- k ⇒ 当出现前缀和相同时维护一个最大的长度。

思路1:(x)

  • 维护一个prefixSum表。遍历nums
  • 用两个for循环,遍历所有子数组。

思路2:

  • 用一个map记录前缀和和第一次出现的位置。key⇒value 的形式。
  • map.has 意味着出现了前缀和一致的情况,则维护最大长度。
/*** @param {number[]} nums* @return {number}*/
var findMaxLength = function(nums) {let max = 0;// 如果连续子数组索引从0开始,则是priefix-prefix[-1],因此要提前保存-1,但是很难想到。const map = new Map();map.set(0,-1)let sum= 0;for (let i = 0; i < nums.length; i++) {if (nums[i] === 0) {sum--; // 遇到0 则-1,相当于把0元素简化为-1} else {sum++;}if (map.has(sum)) {// 出现了相同的前缀和,相减=0,说明这个区域和为0,说明0和1的个数相同max = Math.max(max, i - map.get(sum));// 不用更新sum的索引,因为要求的是最大的} else {map.set(sum, i);}}return max;
};

思路3:

最长的连续子数组是以index = 0 为开头的特殊情况,要么使用思路二,在map里添加 index = -1 的情况。

要么使用思路三:sum = 0 的情况,sum是从index = 0 开始算的,相当于算的就是每个以index = 0 为开头的连续子数组的和。

/*** @param {number[]} nums* @return {number}*/
var findMaxLength = function(nums) {let max = 0;const map = new Map();let sum = 0;for (let i = 0; i < nums.length; i++) {if (nums[i] === 0) {sum --;} else {sum ++;}if(sum === 0){max = Math.max(max,i+1)}else if (map.has(sum)) {max = Math.max(max, i - map.get(sum));} else {map.set(sum , i);}}return max;
};

相关文章:

【LeetCode每日一题】525连续数组 303区域和检索(前缀和的基本概念和3个简单案例)

前缀和 // 构造prefix let prefix [0] arr.forEach(num > {prefix.push(prefix.at(-1) num); })如果想要计算某个区间 i 到 j 这个子数组的和时&#xff0c;可以根据 prefix[j1] - prefix[i] 获得。 例题1&#xff1a;303.区域和检索 - 数组不可变 给定一个整数数组 num…...

形态学算法应用之连通分量提取的python实现——图像处理

原理 连通分量提取是图像处理和计算机视觉中的一项基本任务&#xff0c;旨在识别图像中所有连通区域&#xff0c;并将它们作为独立对象处理。在二值图像中&#xff0c;连通分量通常指的是所有连接在一起的前景像素集合。这里的“连接”可以根据四连通或八连通的邻接关系来定义…...

Kafka系列之:Kafka集群同时设置基于时间和日志大小两种方式保存Topic的数据

Kafka系列之:Kafka集群同时设置基于时间和日志大小两种方式保存Topic的数据 一、基于日志大小二、基于时间大小三、参数设置四、设置命令一、基于日志大小 "log.retention.bytes"是Apache Kafka中的一项配置参数,用于指定每个日志段文件的最大大小。当日志段文件的…...

pytest+allure批量执行测试用例

在 Pytest 中,可以使用装饰器 `@pytest.fixture` 来定义用例级别的前置和后置操作。下面是一个示例代码,演示了如何使用 Pytest 的前置和后置操作: ```python import pytest @pytest.fixture(scope="function") def setup_function(): print("Setup fu…...

SpringBoot和SpringMVC

目录 一、springboot项目 &#xff08;1&#xff09;创建springboot项目 &#xff08;2&#xff09;目录介绍 &#xff08;3&#xff09;项目启动 &#xff08;4&#xff09;运行一个程序 &#xff08;5&#xff09;通过其他方式创建和运行springboot项目 二、SpringMVC…...

免费搭建幻兽帕鲁服务器,白嫖阿里云游戏服务器

阿里云幻兽帕鲁服务器免费搭建方案&#xff0c;先在阿里云高校计划「云工开物」活动领取学生专享300元无门槛代金券&#xff0c;幻兽帕鲁专用服务器4核16G配置26元1个月、149元半年&#xff0c;直接使用这个无门槛300元代金券抵扣即可免费搭建幻兽帕鲁服务器。阿里云服务器网al…...

[技术杂谈]如何下载vscode历史版本

网站模板&#xff1a; https://code.visualstudio.com/updates/v1_85 如果你想下载1.84系列可以访问https://code.visualstudio.com/updates/v1_84​​​​​​ 然后看到&#xff1a; 选择对应版本下载即可&#xff0c;我是windows x64系统选择x64即可开始下载...

nginx slice模块的使用和源码分析

文章目录 1. 为什么需要ngx_http_slice_module2. 配置指令3. 加载模块4. 源码分析4.1 指令分析4.2 模块初始化4.3 slice模块的上下文4.2 $slice_range字段值获取4.3 http header过滤处理4.4 http body过滤处理5 测试和验证 1. 为什么需要ngx_http_slice_module 顾名思义&#…...

AI应用开发-python实现redis数据存储

AI应用开发相关目录 本专栏包括AI应用开发相关内容分享&#xff0c;包括不限于AI算法部署实施细节、AI应用后端分析服务相关概念及开发技巧、AI应用后端应用服务相关概念及开发技巧、AI应用前端实现路径及开发技巧 适用于具备一定算法及Python使用基础的人群 AI应用开发流程概…...

2024年Java架构篇之设计模式

2024年Java实战面试题_java 5 年 面试-CSDN博客 1、单例模式...

搭建macOS开发环境-1:准备工作

请记住&#xff1a; 最重要的准备工作永远是&#xff1a;备份数据 !!! 通过图形界面检查 Mac 的 CPU 类型&#xff1a; 在搭载 Apple 芯片的 Mac 电脑上&#xff0c;“关于本机”会显示一个标有“芯片”的项目并跟有相应芯片的名称&#xff1a; 通过命令行检查Mac的CPU类型 …...

【Makefile语法 02】Makefile语法基础

目录 一、Makefile概述 二、Makefile变量 三、Makefile符号 一、Makefile格式 1. 基本格式&#xff1a; targets : prerequisties [tab键]command target&#xff1a;目标文件&#xff0c;可以是 OjectFile&#xff0c;也可以是执行文件&#xff0c;还可以是一个标签&…...

如何写一个其他人可以使用的GitHub Action

前言 在GitHub中&#xff0c;你肯定会使用GitHub Actions自动部署一个项目到GitHub Page上&#xff0c;在这个过程中总要使用workflows工作流&#xff0c;并在其中使用action&#xff0c;在这个使用的过程中&#xff0c;总会好奇怎么去写一个action呢&#xff0c;所以&#xff…...

排序算法的时间复杂度存在下界问题

对于几种常用的排序算法&#xff0c;无论是归并排序、快速排序、以及更加常见的冒泡排序等&#xff0c;这些排序算法的时间复杂度都是大于等于O(n*lg(n))的&#xff0c;而这些排序算法存在一个共同的行为&#xff0c;那就是这些算法在对元素进行排序的时候&#xff0c;都会进行…...

详解洛谷P2016 战略游戏/BZOJ0495. 树的最小点覆盖之战略游戏(贪心/树形DP)

Description Bob喜欢玩电脑游戏&#xff0c;特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡&#xff0c;城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵&#xff0c;使得这些士兵能了望到所有的路。 注意&…...

解决The Tomcat connector configured to listen on port 8080 failed to start

问题 启动javar报错&#xff0c;提示如下 Description: The Tomcat connector configured to listen on port 8080 failed to start. The port may already be in use or the connector may be misconfigured. Action: Verify the connector’s configuration, identify a…...

深度学习自然语言处理(NLP)模型BERT:从理论到Pytorch实战

文章目录 深度学习自然语言处理&#xff08;NLP&#xff09;模型BERT&#xff1a;从理论到Pytorch实战一、引言传统NLP技术概览规则和模式匹配基于统计的方法词嵌入和分布式表示循环神经网络&#xff08;RNN&#xff09;与长短时记忆网络&#xff08;LSTM&#xff09;Transform…...

C语言的循环结构

目录 前言 1.三种循环语句 1.while循环 2.for循环 2.1缺少表达式的情况 3.do while循环 2.break语句和continue语句 2.1在while循环中 2.2在for循环中 2.3在do while 循环中 3.循环的嵌套 4.go to语句 前言 C语⾔是结构化的程序设计语⾔&#xff0c;这⾥的结构指的是…...

C#用Array类的FindAll方法和List<T>类的Add方法按关键词在数组中检索元素并输出

目录 一、使用的方法 1. Array.FindAll(T[], Predicate) 方法 &#xff08;1&#xff09;定义 &#xff08;2&#xff09;示例 2.List类的常用方法 &#xff08;1&#xff09;List.Add(T) 方法 &#xff08;2&#xff09;List.RemoveAt(Int32) 方法 &#xff08;3&…...

【前后端接口AES+RSA混合加解密详解(vue+SpringBoot)附完整源码】

前后端接口AES+RSA混合加解密详解(vue+SpringBoot) 前后端接口AES+RSA混合加解密一、AES加密原理和为什么不使用AES加密二、RSA加密原理和为什么不使用rsa加密三、AES和RSA混合加密的原理四、代码样例前端1. 请求增加加密标识2. 前端加密工具类3.前端axios请求统一封装,和返…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...