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

本文主要是介绍【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个简单案例)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/694619

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

Hadoop企业开发案例调优场景

需求 (1)需求:从1G数据中,统计每个单词出现次数。服务器3台,每台配置4G内存,4核CPU,4线程。 (2)需求分析: 1G / 128m = 8个MapTask;1个ReduceTask;1个mrAppMaster 平均每个节点运行10个 / 3台 ≈ 3个任务(4    3    3) HDFS参数调优 (1)修改:hadoop-env.sh export HDFS_NAMENOD

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

【区块链 + 人才服务】可信教育区块链治理系统 | FISCO BCOS应用案例

伴随着区块链技术的不断完善,其在教育信息化中的应用也在持续发展。利用区块链数据共识、不可篡改的特性, 将与教育相关的数据要素在区块链上进行存证确权,在确保数据可信的前提下,促进教育的公平、透明、开放,为教育教学质量提升赋能,实现教育数据的安全共享、高等教育体系的智慧治理。 可信教育区块链治理系统的顶层治理架构由教育部、高校、企业、学生等多方角色共同参与建设、维护,支撑教育资源共享、教学质量评估、