【Java算法专场】前缀和(上)

前言

  在求数组或者矩阵求和等问题,我们如果采用暴力解法,时间复杂度可能会达到O(n)或者更高,因此,我们可利用前缀和来解决。

前缀和

前缀和是指序列中的n项和,相当于数学问题中秋数列的前n项和。主要用于数组或列表中求解子数组的和、查询区间和等问题,能够将时间复杂度从O(n)降低到O(1)

接下来我们就通过题目来更好的来理解前缀和。

【模板】前缀和

算法分析

本道题就是在长度为n的数组中根据输入的区间下标[L,R]来计算区间和。如果我们使用暴力解法,时间复杂度为O(n),但是我们有更优的解法,使用前缀和,能使查询区间和的复杂度降为O(1).

算法步骤

  1. 初始化:根据题目需求,定义变量n,q,l,r,并等待输入。定义数组a长度为(n+1),同理,这里需要借助一个前缀和数组dp,长度也为(n+1);
  2. 预处理:给n,q,数组元素,l,r赋值之后,就可以进行下步操作。
  3. 处理前缀和数组:前缀和数组顾名思义就是用来计算前缀和的大小,(前缀和数组中dp[i]指的是包括i在内之前的元素之和),如果我们每次计算dp[i]都要遍历到i,时间复杂度为O(N^2),但我们可以知道的是,每次计算前缀和,都是dp[i-1]+a[i](即i之前的前缀和+a[i]).所以我们计算前缀和dp[i]=dp[i-1]+a[i]
  4. 计算区间和:当我们处理完前缀和数组之后,计算[L,R] 的区间和,我们可以理解为计算(R)之前的和减去(L-1)之前的和,即sum=dp[r]-dp[l-1]
  5. 处理边界:我们这里计算前缀和时,数组下标应该从1开始,若从0开始,当计算前缀和数组dp[0]=dp[-1]+a[0],就会越界,因此下标应该从1开始。且a[0]=dp[0]=0.
  6. 变量类型:通过题目要求,0<=a[i]<=10^9,因此我们不能使用int类型,而是使用long

算法代码

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int q = in.nextInt();long[] a = new long[n + 1];long[] dp = new long[n + 1];a[0] = dp[0] = 0;for (int i = 1; i <= n; i++) {a[i] = in.nextLong();}//处理前缀和数组for (int i = 1; i <= n; i++) {dp[i] = dp[i - 1] + a[i];}//计算区间和while (q > 0) {int l = in.nextInt();int r = in.nextInt();long sum = dp[r] - dp[l - 1];System.out.println(sum);q--;}}
}

时间复杂度为O(n+q),n是数组长度,q是查询次数。

空间复杂度为为O(n),需要借助dp数组。

算法示例

8 1
3 4 5 8 2 3 4 5
4 7

为例 

第一步:初始化 、并预处理a数组

根据输入的值:n=8,q=1 a[9]={0,3,4,5,8,2,3,4,5}

第二步:处理前缀和数组

dp[9]={0,3,7,12,20,22,25,29,35}

第三步:根据L和R计算前缀和 

在输入中,我们可以得到L=4,R=7

所以前缀和sum=dp[7]-d[3]=29-12=17

我们可以测试一下,可以看到,结果确实与我们算的一致。

【模板】

根据这道题目,我们可以总结出计算前缀和时的模板:

 【模板】二维前缀和

 算法分析

本道题是要在一个矩阵中求子矩阵的和,如果我们使用暴力解法,时间复杂度为O(n*m*q),会超时,但对于这种求子矩阵和的问题,我们可以使用前缀和来解决。

在说算法步骤之前,先来补充个知识,我们在计算一个矩阵的大小时,其实是可以将分为几部分来求解的,对于本道题的矩阵,我们可以分解为:

算法步骤

  1. 初始化:定义n和m,并创建(n+1)*(m+1)的二维数组a和(n+1)*(m+1)的二维前缀和数组dp。这里是为了防止溢出。同时也需要创建一个(n+1)*(m+1)的前缀和矩阵。
  2. 矩阵处理:在上面的图片中,我们知道了一个矩阵可以切块计算。那么我们在计算dp[i][j]的时候,其实也是可以分成4部分。我们在计算A部分的时候,是很容易计算的(其实就是dp[i-1][j-1]的和),但我们想要知道B、C部分的和,那是有点困难的,但我们可以看出,如果我们把A和B、A和C结合来,其实就是前缀和dp[i-1][j]和dp[i][j-1],这从我们前缀和数组中是可以知道的。所以,我们在处理前缀和矩阵的时候,可以根据公式:

dp[i][j]=dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1]

即S=(A+B)+(A+C)+D-A

3.计算子矩阵和:当我们处理完前缀和矩阵之后,就可以利用矩阵来进行求和。

根据所给的坐标(X1,Y1),(X2,Y2),我们可以得到以下:

同理的,我们根据坐标,将矩阵分为4部分,其中D矩阵就是我们所要求的子矩阵。我们想要求D的话,根据

D=(A+B+C+D)-(A+B)-(A+C)+A

  =dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

即可得到。

算法代码 

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int q=sc.nextInt();long[][] a=new long[n+1][m+1];long[][] dp=new long[n+1][m+1];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=sc.nextLong();}}//预处理矩阵for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//S=(A+B)+(A+C)+D-Adp[i][j]=dp[i-1][j]+dp[i][j-1]+a[i][j]-dp[i-1][j-1];}}//求子矩阵和while(q>0){int x1=sc.nextInt();int y1=sc.nextInt();int x2=sc.nextInt();int y2=sc.nextInt();//sum=(A+B+C+D)-(A+B)-(A+C)+A=Dlong sum=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];System.out.println(sum);q--;}}
}

时间复杂度为O(n*m)+O(q),n,m为二维数组的行,列,q为查询次数。

空间复杂度为O(n*m).需要开辟两个数组,a和dp。 

算法示例

3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2

为例

第一步:初始化

根据输入的值,可以得到:

n=3,m=4,q=3  

a数组如下 

第二步:处理前缀和矩阵

根据二维数组a,我们可以计算出前缀和数组dp为

【模板】

寻找数组的中心下标

算法分析 

这道题是要我们在数组中,找以一个点为中心,左右区间和相等。这里我们可以利用前缀和来进行解答。这里我们需要利用到两个数组,yp和np。

算法步骤

  1. 初始化:定义n,并初始化为nums.length.定义两个二维数组yp(前缀合)和np(后缀和)并设置长度为n;yp用来存储从前往后的和,np用来存储从后往前的和。
  2. 预处理yp和np:yp从1开始往后遍历,yp=yp[i-1]+nums[i-1],循环条件为:i<n;np从nums.length-2开始,np[i]=np[i+1]+nums[i+1],循环条件为:i>=0.
  3. 判断:当处理完yp和np之后,我们就可判断yp和np中数组元素是否相等,若相等,证明以该点为中心点的左右区间和相等,返回此时的下标即可。当遍历完数组,若没有相等的,则返回-1.

算法代码

    /*** 寻找数组的中心索引* 中心索引的左侧元素之和等于右侧元素之和* * @param nums 输入的整数数组* @return 返回中心索引,如果不存在,则返回-1*/public int pivotIndex(int[] nums) {// 数组长度int n=nums.length;// yp数组用于存储从左侧累加的元素之和int[] yp=new int[n];// np数组用于存储从右侧累加的元素之和int[] np=new int[n];// 从左侧开始累加,计算每个位置左侧元素之和for(int i=1;i<n;i++){yp[i]=yp[i-1]+nums[i-1];}// 从右侧开始累加,计算每个位置右侧元素之和for(int i=n-2;i>=0;i--){np[i]=np[i+1]+nums[i+1];}// 遍历数组,寻找中心索引for(int i=0;i<n;i++){// 当找到左右两侧元素之和相等的位置时,返回该索引if(yp[i]==np[i]){return i;}}// 如果没有找到中心索引,返回-1return -1;}

算法示例:

以nums = [1, 7, 3, 6, 5, 6]为例

第一步:初始化

n=6

第二步:预处理

yp={0,1,8,11,16,21}

np={27,20,17,11,6,0}

第三步:判断

我们可以看到,yp[3]=np[3]=11,此时返回下标3即可。

除自身以外数组的乘积

 算法分析

本道题与上一道题类似,不过这道题是为了求除当前下标的数,其他数的乘积。那么这道题我们照样可以用前缀和。这里同样需要两个数组,前缀和数组yp,后缀和数组np。

算法步骤

  1. 初始化:定义n,并初始化为nums.length,yp和np数组的长度设置为n。
  2. 预处理数组:与上道题循环条件,起始位置一致。yp[i]=yp[i-1]+nums[i-1]. np[i]=np[i+1]+nums[i+1].(需要注意的是这里yp[0]和np[n-1]都需要初始化为1,否则相乘时会导致数据出错)
  3. 数组相乘:这里需要设置数组ans并设置长度为n,用来存储前缀和和后缀和的乘积。
  4. 返回结果:当前缀和和后缀合相乘完并存储在ans后,返回ans即可。

算法代码

/*** 计算数组中每个元素的乘积,排除自身* 这个方法通过使用两个辅助数组来优化计算,避免了对每个元素重复遍历整个数组求乘积的过程* * @param nums 原始整数数组* @return 包含每个元素对应位置上的乘积结果的数组*/
public int[] productExceptSelf(int[] nums) {// 数组长度int n = nums.length;// yp数组用于存储每个位置左侧所有数字的乘积int[] yp = new int[n];// np数组用于存储每个位置右侧所有数字的乘积int[] np = new int[n];// 初始化左侧乘积数组,yp[0]为1,因为第一个元素左侧没有元素,乘积为1yp[0] = 1;for (int i = 1; i < n; i++) {yp[i] = yp[i - 1] * nums[i - 1];}// 初始化右侧乘积数组,np[n-1]为1,因为最后一个元素右侧没有元素,乘积为1np[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {np[i] = np[i + 1] * nums[i + 1];}// 构建答案数组,每个元素是对应位置的左侧乘积和右侧乘积的乘积int[] ans = new int[n];for (int i = 0; i < n; i++) {ans[i] = yp[i] * np[i];}return ans;
}

时间复杂度为O(n),n为数组长度。

空间复杂度为O(n)

算法示例

以nums = [1,2,3,4]为例

第一步:初始化

n=4

第二步:处理缀合数组

根据yp[i]=yp[i-1]+nums[i-1]可得

yp={1,1,2,6}

根据np[i]=np[i+1]+nums[i+1]可得

np={24,12,4,1}

第三步:缀合数组相乘

ans={24,12,8,6}

第四步:返回结果

此时将ans数组返回即可。


前缀和上篇就先到这里了~

若有不足,欢迎指正~ 

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

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

相关文章

ElasticSearch入门(六)SpringBoot2

private String author; Field(name “word_count”, type FieldType.Integer) private Integer wordCount; /** Jackson日期时间序列化问题&#xff1a; Cannot deserialize value of type java.time.LocalDateTime from String “2020-06-04 15:07:54”: Failed to des…

【C++】学习笔记——C++的类型转换

文章目录 二十三、C的类型转换1. C语言中的类型转换2. C类型转换static_castreinterpret_castconst_castdynamic_cast 未完待续 二十三、C的类型转换 1. C语言中的类型转换 在C语言中&#xff0c;如果赋值运算符左右两侧类型不同&#xff0c;或者形参与实参类型不匹配&#x…

声学改造后的气膜馆:提升体验的独特优势—轻空间

气膜馆因其快速建造、低成本和灵活性&#xff0c;近年来广泛应用于各种运动和活动场所。然而&#xff0c;传统气膜馆在声学表现上存在一些挑战&#xff0c;例如回声和噪音的控制。随着声学改造技术的应用&#xff0c;气膜馆的声学环境得到了显著改善。轻空间将探讨声学改造后的…

轨迹优化 | 基于ESDF的共轭梯度优化算法(附ROS C++/Python仿真)

目录 0 专栏介绍1 数值优化:共轭梯度法2 基于共轭梯度法的轨迹优化2.1 障碍约束函数2.2 曲率约束函数2.3 平滑约束函数3 算法仿真3.1 ROS C++实现3.2 Python实现0 专栏介绍 🔥课设、毕设、创新竞赛必备!🔥本专栏涉及更高阶的运动规划算法轨迹优化实战,包括:曲线生成、…

2024年对初学者友好的4款视频剪辑软件不容错过

在这个视觉当道的时代&#xff0c;视频剪辑不再是专业人士的专属领域。随着技术的进步&#xff0c;现在即使是初学者也能轻松上手&#xff0c;发挥自己的创意。今天&#xff0c;我来给大家推荐四款在2024年非常适合初学者使用的视频剪辑软件&#xff0c;让你的创意能够在指尖轻…

Duplicate class kotlin.collections.jdk8.CollectionsJDK8Kt found in modules。Android studio纯java代码报错

我使用java代码 构建项目&#xff0c;初始代码运行就会报错。我使用的是Android Studio Giraffe&#xff08;Adroid-studio-2022.3.1.18-windows&#xff09;。我在网上找的解决办法是删除重复的类&#xff0c;但这操作起来真的太麻烦了。 这是全部报错代码&#xff1a; Dupli…

VLC实现视频文件转RTSP流

1.选择本地文件 2.创建流 现在已经开始推流了&#xff1a; 3.播放上面创建的流 访问地址&#xff1a;rtsp://:8554/test111

dfs,CF 196B - Infinite Maze

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 https://codeforces.com/problemset/problem/196/B 二、解题报告 1、思路分析 考虑如何判断一条路径可以无限走&#xff1f; 我们对朴素的网格dfs改进&#xff0c;改进为可以dfs网格外的区域 如果存在某个…

免费分享:全国传统村落空间分布数据(附下载方法)

数据简介 本数据是在中国传统村落名录的基础上&#xff0c;通过地理编码&#xff0c;制作成具有空间坐标信息的矢量数据。 数据属性 数据名称&#xff1a;全国传统村落空间分布数据数据时间&#xff1a;2012年至今&#xff0c;更新至第五批空间位置&#xff1a;全国数据格式&…

模拟自然光照:饮料稳定性测试的创新方法

饮料添加剂的光照稳定性测试旨在评估其在光照影响下的保持稳定性的能力&#xff0c;特别是在储存期间。此测试有助于制造商理解饮料在不同光源作用下的变化&#xff0c;例如颜色、口感、香气等感官性质的变化&#xff0c;以及营养成分的衰变速率。这些信息对改进产品配方、包装…

与树莓派的“黄金”关系,是如何帮助这家医疗设备公司扩大规模

稳定的供应和与Raspberry Pi的“黄金”关系帮助医疗设备公司进行了规模扩张 埃及医疗设备制造商Bio Business需要将物联网功能集成到其成功的患者监测设备系列中。Raspberry Pi技术使他们得以实现。 解决方案 RP2040 Compute Module 4 企业规模 中小企业 行业 医疗技术 …

怎么挑选适合企业的安全管理软件?2024值得推荐的5款安全管理软件?

在企业安全管理时&#xff0c;你是否遇到过以下问题&#xff1a; 工作点多面广&#xff0c;信息整理和分析的工作量大&#xff0c;手工处理繁杂耗时&#xff1b; 传统巡检方式&#xff0c;无法保证巡检过程结果真实性&#xff1b; 纸质记录不清晰&#xff0c;问题改进缺乏数…

使用SpaceDesk实现iPad成为电脑拓展屏(保姆级教程)

使用SpaceDesk实现iPad成为电脑拓展屏 SpaceDesk是一个开源的软件, 所以说对学生和平民用户非常的友好, 连接后的画质也非常不错, 而且具有无线和有线两种连接方式. 接下来就开始教程: 1. 安装SpaceDesk电脑版 首先我们要下载SpaceDesk电脑版安装好: SpaceDesk官网 注意: …

2006-2022年中国农村经营管理年报

2006-2022年中国农村经营管理年报 1、时间&#xff1a;2006-2022年 2、格式&#xff1a;2006-2014年为EXCEL&#xff0c;2015-2022年为PDF 3、说明&#xff1a;根据农村经营管理情况统计报表制度调查数据整理、编辑的。本资料系统收录了全国各省、自治区、直辖市农村集体经济…

https执行过程,特点,作用

还是大剑师兰特&#xff1a;曾是美国某知名大学计算机专业研究生&#xff0c;现为航空航海领域高级前端工程师&#xff1b;CSDN知名博主&#xff0c;GIS领域优质创作者&#xff0c;深耕openlayers、leaflet、mapbox、cesium&#xff0c;canvas&#xff0c;webgl&#xff0c;ech…

【Spring Boot】手撕搜索引擎项目,深度复盘在开发中的重难点和总结(长达两万6千字的干货,系好安全带,要发车了......)

目录 搜索引擎搜索引擎的核心思路 一、解析模块1.1 枚举所有文件1.2 解析每个文件的标题&#xff0c;URL以及正文1.2.1 解析标题1.2.2 解析URL1.2.3 解析正文 1.3 线程池优化代码 二 、创建排序模块2.1 构建正排索引2.2 构建倒排索引2.3 序列化2.4 反序列化 三、搜索模块3.1 引…

86. UE5 RPG 技能面板实现监听数据

在上一篇文章里&#xff0c;我们创建了技能面板的控制器&#xff0c;接下来&#xff0c;我们将实现通过控制器绑定委托&#xff0c;来更新显示内容。 更新技能面板应用的技能 我们首先更新技能面板上面已经应用的技能&#xff0c;让其和WBP_Overlay上面一样&#xff0c;可以更…

ELK+filebeat

ELKfilebeat 一、filebeat概述 1、filebeat概念&#xff1a; filebeat日志收集工具和logstash相同 filebeat是一款轻量级的日志收集工具&#xff0c;可以在非JAVA环境下运行。 因此&#xff0c;filebeat常被用在非JAVAf的服务器上用于替代Logstash&#xff0c;收集日志信息。…

产品经理NPDP好考吗?

NPDP是新产品开发专业人员的资格认证&#xff0c;对于希望在产品管理领域取得认可的专业人士来说&#xff0c;NPDP认证是一项重要的资格。 那么&#xff0c;产品经理考取NPDP资格认证究竟难不难呢&#xff1f; 首先&#xff0c;NPDP考试的难易程度取决于考生的背景和准备情况…

谷粒商城实战笔记-105~107-全文检索-ElasticSearch-入门

文章目录 一&#xff0c;105-全文检索-ElasticSearch-入门-_cat二&#xff0c;106-全文检索-ElasticSearch-入门-put&post新增数据三&#xff0c;107-全文检索-ElasticSearch-入门-get查询数据&乐观锁字段1&#xff0c;过时的乐观锁-version2&#xff0c;Elasticsearch…