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

易联网站建设/谷歌网页

易联网站建设,谷歌网页,做网站要域名吗,招聘网站开发源码前缀和 // 构造prefix let prefix [0] arr.forEach(num > {prefix.push(prefix.at(-1) num); })如果想要计算某个区间 i 到 j 这个子数组的和时,可以根据 prefix[j1] - prefix[i] 获得。 例题1:303.区域和检索 - 数组不可变 给定一个整数数组 num…

前缀和

在这里插入图片描述

// 构造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请求统一封装,和返…...

React环境配置

1.安装Node.js Node.js官网&#xff1a;https://nodejs.org/en/ 下载之后按默认选项安装好 重启电脑即可自动完成配置 2.安装React 国内使用 npm 速度很慢&#xff0c;可以使用淘宝定制的 cnpm (gzip 压缩支持) 命令行工具代替默认的 npm。 ①使用 winR 输入 cmd 打开终端 ②依…...

Pandas 数据处理-排序与排名的深度探索【第69篇—python:文本数据处理】

文章目录 Pandas 数据处理-排序与排名的深度探索1. sort_index方法2. sort_values方法3. rank方法4. 多列排序5. 排名方法的参数详解6. 处理重复值7. 对索引进行排名8. 多级索引排序与排名9. 更高级的排序自定义10. 性能优化技巧10.1 使用nsmallest和nlargest10.2 使用sort_val…...

第8节、双电机多段直线运动【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;前面章节主要介绍了bresenham直线插值运动&#xff0c;本节内容介绍让两个电机完成连续的直线运动,目标是画一个正五角星 一、五角星图介绍 五角星总共10条直线&#xff0c;10个顶点。设定左下角为原点…...

Elasticsearch:基本 CRUD 操作 - Python

在我之前的文章 “Elasticsearch&#xff1a;关于在 Python 中使用 Elasticsearch 你需要知道的一切 - 8.x”&#xff0c;我详细讲述了如何建立 Elasticsearch 的客户端连接。我们也详述了如何对数据的写入及一些基本操作。在今天的文章中&#xff0c;我们针对数据的 CRUD (cre…...

1992-2022年全国及31省对外开放度测算数据(含原始数据+计算结果)(无缺失)

1992-2022年全国及31省对外开放度测算数据&#xff08;含原始数据计算结果&#xff09;&#xff08;无缺失&#xff09; 1、时间&#xff1a;1992-2022年 2、来源&#xff1a;各省年鉴、国家统计局、统计公报、 3、指标&#xff1a;进出口总额&#xff08;万美元&#xff09…...

JVM之GC垃圾回收

GC垃圾回收 如何判断对象可以回收 引用计数法 如果有对象引用计数加一&#xff0c;没有对象引用&#xff0c;计数减一&#xff0c;如果计数为零&#xff0c;则回收 但是如果存在循环引用&#xff0c;即A对象引用B对象&#xff0c;B对象引用A对象&#xff0c;会造成内存泄漏 可…...

自然语言学习nlp 六

https://www.bilibili.com/video/BV1UG411p7zv?p118 Delta Tuning&#xff0c;尤其是在自然语言处理&#xff08;NLP&#xff09;和机器学习领域中&#xff0c;通常指的是对预训练模型进行微调的一种策略。这种策略不是直接更新整个预训练模型的权重&#xff0c;而是仅针对模型…...

fpga 需要掌握哪些基础知识?

个人根据自己的一些心得总结一下fpga 需要掌握的基础知识&#xff0c;希望对你有帮助。 1、数电&#xff08;必须掌握的基础&#xff09;&#xff0c;然后进阶学模电&#xff0c; 2、掌握HDL&#xff08;verilog或VHDL&#xff09;一般建议先学verilog&#xff0c;然后可以学…...

Qt未来市场洞察

跨平台开发&#xff1a;Qt作为一种跨平台的开发框架&#xff0c;具有良好的适应性和灵活性&#xff0c;未来将继续受到广泛应用。随着多设备和多平台应用的增加&#xff0c;Qt的前景在跨平台开发领域将更加广阔。 物联网应用&#xff1a;由于Qt对嵌入式系统和物联网应用的良好支…...

GPT-4模型中的token和Tokenization概念介绍

Token从字面意思上看是游戏代币&#xff0c;用在深度学习中的自然语言处理领域中时&#xff0c;代表着输入文字序列的“代币化”。那么海量语料中的文字序列&#xff0c;就可以转化为海量的代币&#xff0c;用来训练我们的模型。这样我们就能够理解“用于GPT-4训练的token数量大…...