数据结构与算法-前缀和数组

前缀和问题

什么是前缀和?

对于一个一般数组 nums,如果我们需要知道 S1 = nums[0] + nums[1]的结果, S2= nums[0] + nums[1] + nums[2] …

计算公式相当于: S2 = S1 + nums[2] … Sn = Sn-1 + nums[n];

所谓前缀和:用来记录数组前项和的一个新数组,提高计算求和的效率。

image-20241108170603096

从普通数组转向前缀和数组

image-20241108171402449

一般递推公式

由前缀和的定义我们可以得出以下前缀和公式:

当前项i的前缀和S[i]
S[i] = S[i-1] + nums[i-1];
当前项i的数据由前缀和推出
nums[i-1] = S[i] - S[i-1]
代码实现
int[] nums = {2,5,1,7,3,6};
int[] s = new int[nums.length+1];for(int i= 1;i<s.length;i++){s[i] = s[i-1]+ nums[i-1];
}System.out.println(Arrays.toString(nums));
System.out.println(Arrays.toString(s));

输出结果

[2, 5, 1, 7, 3, 6]
[0, 2, 7, 8, 15, 18, 24]
扩展运用

计算指定位置之间的数据和。

假设数组为 {1,2, 3, 4}, 位置1,3之间的和为: 2+3+4 = 9

使用前缀和

列出前缀和数组: {0,1, 3, 6, 10} , 位,1到3之间的和 S[4]- S[1] = 10 -1 = 9

计算任意位置之间的和: S[i+1] - S[j] , tips: 前缀和数组的S[0] =0;

力扣问题

1480. 一维数组的动态和 - 力扣(LeetCode)

class Solution {public int[] runningSum(int[] nums) {int[] s = new int[nums.length];s[0] = nums[0];for (int i = 1; i < s.length; i++) {s[i] = s[i - 1] + nums[i];}return s;}
}

303. 区域和检索 - 数组不可变 - 力扣(LeetCode)

class NumArray {private int[] nums;private int[] s;public NumArray(int[] nums) {this.nums = nums;this.s = new int[nums.length + 1];for (int i = 1; i < s.length; i++) {s[i] = s[i - 1] + nums[i - 1];}}public int sumRange(int left, int right) {return s[right+1] - s[left];}
}

560. 和为 K 的子数组 - 力扣(LeetCode)

二维数组前缀和

二维数组的前缀和 S[X][Y] = nums[0][0] + … nums[X-1][Y-1]

构建前缀和数组

假设原数组nums[m][n],前缀和数组 S[m+1][n+1],预留第0行,第1列不用。

image-20241109082158826
计算前缀和数组第一行S[0][Y]

前缀和的第一行即为原数组的第一行求和(类似一维数组求和),初始化前缀和数组。

S[0][y] = nums[0][0] + .... nums[0][y-1]

image-20241109082336784

构建前缀和第二行

image-20241109082759601

构建第三行

image-20241109082902209

最终形态
image-20241109083005864
前项和公式

我们观察S[3][3]

S[3][3] =  nums[0][0] + nums[0][1] + nums[0][2]+ nums[1][0] + nums[1][1] + nums[1][2]+ nums[2][0] + nums[2][1] + nums[2][2]=  nums[0][0] + nums[0][1] + nums[0][2] + nums[1][0] + nums[1][1] + nums[1][2]+ nums[0][0] + nums[0][1] + nums[1][0] + nums[1][1] + nums[2][0] + nums[2][1]+ nums[2][2] - nums[0][0] - nums[0][1] - nums[1][0] - nums[1][1]

image-20241112160258294

S[i , j] = S[i-1][j] + S[i][j-1] + nums[i][j] - S[i-1][j-1]

image-20241112160820195

前缀和例题

二维区域和检索 - 矩阵不可变

问题

304. 二维区域和检索 - 矩阵不可变 - 力扣(LeetCode)

问题描述

给定一个二维矩阵 matrix,以下类型的多个请求:

  • 计算其子矩形范围内元素的总和,该子矩阵的 左上角(row1, col1)右下角(row2, col2)

实现 NumMatrix 类:

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1)右下角 (row2, col2) 所描述的子矩阵的元素 总和

示例 1:

img

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
解决方案
构建前缀和

image-20241112165304526

求阴影部分的值

由图我们观察到阴影部分的可以看做: (0,0)->((row2+1), (col2+1)) - (0,0)->((row1), (col2+1)

​ - (0,0)->((row2+1), (col1) + (0,0)->((row1), (col1) 【此矩形被减去了两次】

image-20241112170405856

s[row2+1][col2+1] - s[row1][col2+1] - s[row2+1][col1] + s[row1][col1];

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

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

相关文章

R语言机器学习与临床预测模型77--机器学习预测常用R语言包

R小盐准备介绍R语言机器学习与预测模型的学习笔记 你想要的R语言学习资料都在这里&#xff0c; 快来收藏关注【科研私家菜】 01 预测模型常用R包 常见回归分析包: rpart 包含有分类回归树的方法; earth 包可以实现多元自适应样条回归; mgev包含广义加性模型回归; Rweka 包中的M…

Elasticsearch可视化工具Elasticvue插件用法

目录 1.打开浏览器扩展程序(示例Edge浏览器) ​2.搜索elasticvue并安装 3.打开elasticvue ​4.连接Es 5.有些浏览器无法下载安装扩展&#xff0c;例如谷歌。可以打包扩展给别的浏览器使用。 5.1打开浏览器扩展&#xff0c;打开开发人员模式&#xff0c;记住扩展程序id 5…

大数据技术之HBase中的HRegion

如果你正在学习大数据&#xff0c;你应该知道HBase是一个列式存储的NoSQL分布式数据库&#xff0c;可以配合Hadoop来使用。今天自己简单做了几页PPT&#xff0c;解释了一下HBase当中HRegion的基本概念&#xff0c;很多初学者在学习的时候对HRegion这个概念一直懵懵懂懂&#xf…

Spring Cloud Contract快速入门Demo

1.什么是Spring Cloud Contract &#xff1f; Spring Cloud Contract 是 Spring 提供的一套工具&#xff0c;用于帮助开发者通过契约&#xff08;Contract&#xff09;驱动的方式进行微服务的测试和集成。它主要解决微服务之间通信时&#xff0c;如何确保服务提供者和消费者之…

GISBox VS ArcGIS:分别适用于大型和小型项目的两款GIS软件

在现代地理信息系统&#xff08;GIS&#xff09;领域&#xff0c;有许多大家耳熟能详的GIS软件。它们各自具有独特的优势&#xff0c;适用于不同的行业需求和使用场景。在众多企业和开发者面前&#xff0c;如何选择合适的 GIS 软件成为了一个值得深入思考的问题。今天&#xff…

Linux 进程线程间通信总结

线程 线程共享存储空间主要带来的问题是数据同步和互斥。由于线程在同一进程中运行&#xff0c;它们共享相同的内存空间&#xff0c;任何线程都可以访问共享数据。这样&#xff0c;多个线程并发执行时&#xff0c;可能会导致以下两种主要问题&#xff1a; 互斥问题&#xff0…

【再谈设计模式】抽象工厂模式~对象创建的统筹者

一、引言 在软件开发的世界里&#xff0c;高效、灵活且易于维护的代码结构是每个开发者追求的目标。设计模式就像是建筑蓝图中的经典方案&#xff0c;为我们提供了应对各种常见问题的有效策略。其中&#xff0c;抽象工厂模式在对象创建方面扮演着重要的角色&#xff0c;它如同一…

Web安全之SQL注入---基础

文章目录 SQL注入简介SQL注入基础SQL注入分类SQL注入流程 SQL注入简介 什么是SQL注入&#xff1f; SQL注入即是指web应用程序对用户输入数据的合法性没有判断或过滤不严&#xff0c;攻击者可以在web应用程序中事先定义好的查询语句的结尾上添加额外的SQL语句&#xff0c;在管理…

机器学习——贝叶斯

&#x1f33a;历史文章列表&#x1f33a; 机器学习——损失函数、代价函数、KL散度机器学习——特征工程、正则化、强化学习机器学习——常见算法汇总机器学习——感知机、MLP、SVM机器学习——KNN机器学习——贝叶斯机器学习——决策树机器学习——随机森林、Bagging、Boostin…

gdb编译教程(支持linux下X86和ARM架构)

1、下载源码 http://ftp.gnu.org/gnu/gdb/ 我下载的8.2版本。 2、下载完后拷贝到linux的x86系统。 3、解压&#xff0c;然后进入到目录下&#xff0c;打开当前目录的命令行窗口。 4、创建一个生成目录。 5、我们先开始x86版本&#xff0c;这个比较简单&#xff0c;不需要配置…

10款翻译工具实践体验感受与解析!!!!!

在现今的数字化时代&#xff0c;翻译工具如同语言的桥梁&#xff0c;为我们打开了通向世界的大门。今天咱们不聊别的&#xff0c;就聊聊那些让我又爱不释手的翻译工具们。因为我的职业因素&#xff0c;作为一个经常需要跟各种语言打交道的“文字搬运工”&#xff0c;这些工具可…

【日志】392.判断子序列

2024.11.8 【力扣刷题】 392. 判断子序列 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/is-subsequence/?envTypestudy-plan-v2&envIdtop-interview-150 整个题从一开始就是打算从双指针的思想往下走的。但是&#xff0c;我设置了四个变量sLeft…

C++20 中最优雅的那个小特性 - Ranges

C20 中最优雅的那个小特性 - Ranges 大家好&#xff0c;今天我们来聊聊 C20 的一项非常重要的新特性——Ranges&#xff0c;可以让你的代码更优雅、更高效、更炫酷&#xff0c;如果你是一个对代码有所追求的小伙伴&#xff0c;那么这个特性你绝对值得拥有&#xff01; 啥是 …

Python多进程间通讯(包含共享内存方式)

文章目录 1 通过非共享内存配合队列方式2 通过共享内存配合队列方式 注&#xff1a;本博文测试环境为Linux系统。 1 通过非共享内存配合队列方式 下面是一个常见的生产者与消费者的模式示例&#xff0c;这里分别启动了两个子进程&#xff0c;一个为生产者&#xff08;producer…

深入理解接口测试:实用指南与最佳实践5.0(一)

✨博客主页&#xff1a; https://blog.csdn.net/m0_63815035?typeblog &#x1f497;《博客内容》&#xff1a;.NET、Java.测试开发、Python、Android、Go、Node、Android前端小程序等相关领域知识 &#x1f4e2;博客专栏&#xff1a; https://blog.csdn.net/m0_63815035/cat…

2024.11.12_大数据的诞生以及解决的问题

大数据的诞生以及解决的问题 视频一&#xff1a;大数据诞生的背景原因&#xff1a;传统的数据处理架构无法满足海量的数据存储和计算需求 视频三&#xff1a;区分离线处理场景和实时处理场景视频五&#xff1a;传统的大数据与现代的大数据区别&#xff08;离线场景&#xff09;…

ML 系列: 第 24 节 — 离散概率分布(泊松分布)

目录 一、说明 二、固定时间间隔示例 三、固定间隔的示例 四、泊松分布的主要特征 五、示例 5.1 平均客户数的计算&#xff1a; 5.2 用于计算和绘制泊松分布的 Python 代码&#xff1a; 一、说明 泊松概率分布是一种离散概率分布&#xff0c;它表示在固定的时间或空间间隔内发生…

闯关leetcode——3174. Clear Digits

大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/clear-digits/description/ 内容 You are given a string s. Your task is to remove all digits by doing this operation repeatedly: Delete the first digit and the closest non-digit cha…

机器情绪及抑郁症算法

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;编程探索专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年11月12日17点02分 点击开启你的论文编程之旅https://www.aspiringcode.com/content?id17230869054974 计算机来理解你的情绪&a…

【深圳大学】数据结构A+攻略(计软版)

1. 考试 1.1 形式 分为平时&#xff0c;笔试&#xff0c;机试三部分。其中&#xff1a; 平时占30%&#xff0c;包含平时OJ测验和课堂练习&#xff0c;注意这个可能会因老师的不同和课题组的新策略而改变。笔试占60%&#xff0c;是分值占比的主要部分。机试占10%。 1.2 题型…