优选算法之前缀和(上)

news/2024/12/23 1:32:57/

目录

一、【模板】一维前缀和

1.题目链接:DP34【模板】前缀和

2.题目描述:

3.解法(前缀和

🍃算法思路:

🍃算法代码:

二、【模板】二维前缀和

1.题目链接:DP35【模板】二维前缀和

2.题目描述:

3.解法(前缀和

🍃算法思路:

🍃算法代码:

三、寻找数组的中心下标

1.题目链接:724. 寻找数组的中心下标

2.题目描述:

3.解法(前缀和

🍒算法思路:

🍒算法代码:

四、除自身以外数组的乘积

1.题目链接:238. 除自身以外数组的乘积

2.题目描述:

3.解法(前缀和

🍒算法思路:

🍒算法代码:


一、【模板】一维前缀和

1.题目链接:DP34【模板】前缀和

2.题目描述:

给定一个长度为n的数组𝑎1,𝑎2,....𝑎𝑛。

接下来有q次查询, 每次查询有两个参数l, r。

对于每个询问, 请输出𝑎𝑙+𝑎𝑙+1+....+𝑎𝑟。

输入描述:

第一行包含两个整数n和q.

第二行包含n个整数, 表示𝑎1,𝑎2,....𝑎𝑛。

接下来q行,每行包含两个整数   l和r.

1≤𝑛,𝑞≤105
−109≤𝑎[𝑖]≤109
1≤𝑙≤𝑟≤𝑛

输出描述:

输出q行,每行代表一次查询的结果.

示例 1:

输入:

3 2
1 2 4
1 2
2 3

输出:

3
6

3.解法(前缀和

🍃算法思路:

a. 先预处理出来一个「前缀和」数组:

用 dp[i] 表示: [1, i] 区间内所有元素的和,那么 dp[i - 1] 里面存的就是 [1, i - 1] 区间内所有元素的和,可得递推公式: dp[i] = dp[i - 1] + arr[i]。

b. 使用前缀和数组,「快速」求出「某⼀个区间内」所有元素的和:

当询问的区间是 [l, r] 时:区间内所有元素的和为: dp[r] - dp[l - 1] 。

🍃算法代码:

#include <iostream>
#include <vector>using namespace std;int main() 
{// 1.读入数据int n = 0, q = 0;cin >> n >> q;vector<int> arr(n + 1);for(int i = 1; i <= n; i++){cin >> arr[i];}// 2.预处理前缀和数组vector<long long> dp(n + 1);// 防止溢出for(int i = 1; i <= n; i++){dp[i] = dp[i - 1] + arr[i];}//3.使用前缀和数组int l = 0, r = 0;while(q--){cin >> l >> r;cout << dp[r] - dp[l - 1] << endl;}return 0;
}

二、【模板】二维前缀和

1.题目链接:DP35【模板】二维前缀和

2.题目描述:

给你一个 n 行 m 列的矩阵 A ,下标从1开始。
接下来有 q 次查询,每次查询输入 4 个参数 x1 , y1 , x2 , y2
请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和

输入描述:

第一行包含三个整数n,m,q.
接下来n行,每行m个整数,代表矩阵的元素
接下来q行,每行4个整数x1, y1, x2, y2,分别代表这次查询的参数

1≤𝑛,𝑚≤1000
1≤𝑞≤105
−109≤𝑎[𝑖][𝑗]≤109
1≤𝑥1≤𝑥2≤𝑛
1≤𝑦1≤𝑦2≤𝑚

输出描述:

输出q行,每行表示查询结果。

示例1

输入:

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

输出:

8
25
32

3.解法(前缀和

🍃算法思路:

        类比于一维数组的形式,如果我们能处理出来从 [0, 0] 位置到 [i, j] 位置这片区域内所有元素的累加和,就可以在 O(1) 的时间内,搞定矩阵内任意区域内所有元素的累加和。因此我们接下来仅需完成两步即可:

这里就要用到一维数组里面的拓展知识,我们要在矩阵的最上面和最左边添加上一行和⼀列 0,这样我们就可以省去非常多的边界条件的处理(大家可以自行尝试直接搞出来前缀和矩阵,边界条件的处理会让你崩溃的)。处理后的矩阵就像这样:

这样,我们填写前缀和矩阵数组的时候,下标直接从 1 开始,能大胆使用i - 1 , j - 1 位置的值。

注意 dp 表与原数组 arr 内的元素的映射关系:

  1. 从 dp 表到 arr 矩阵,横纵坐标减⼀; 
  2. 从 arr 矩阵到 dp 表,横纵坐标加⼀。

前缀和矩阵中 sum[i][j] 的含义,以及如何递推二维前缀和方程

🍁sum[i][j] 的含义:

sum[i][j] 表示,从 [0, 0] 位置到 [i, j] 位置这段区域内,所有元素的累加和。对应下图的红色区域:

🍂递推方程:

其实这个递推方程非常像我们小学做过求图形面积的题,我们可以将 [0, 0] 位置到 [i, j]位置这段区域分解成下面的部分:

 

sum[i][j] = 红 + 蓝 + 绿 + 黄,分析一下这四块区域:

i. 黄色部分最简单,它就是数组中的 arr[i - 1][j - 1] (注意坐标的映射关系);

ii. 单独的蓝不好求,因为它不是我们定义的状态表示中的区域,同理,单独的绿也是;

iii. 但是如果是红 + 蓝,正好是我们 dp 数组中 sum[i - 1][j] 的值,美滋滋;

iv. 同理,如果是红 + 绿,正好是我们 dp 数组中 sum[i][j - 1] 的值;

v. 如果把上面求的三个值加起来,那就是黄 + 红 + 蓝 + 红 + 绿,发现多算了⼀部分红的面积,因此再单独减去红的面积即可;

vi. 红的面积正好也是符合 dp 数组的定义的,即 sum[i - 1][j - 1]。

综上所述,我们的递推方程就是:

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

        题目的接口中提供的参数是原始矩阵的下标,为了避免下标映射错误,这里直接先把下标映射成 dp 表里面对应的下标: row1++, col1++, row2++, col2++。

        接下来分析如何使用这个前缀和矩阵,如下图(注意这里的 row 和 col 都处理过了,对应的正是 sum 矩阵中的下标):

对于左上角 (row1, col1) 、右下角 (row2, col2) 围成的区域,正好是红色的部分。因此我们要求的就是红色部分的面 积,继续分析几个区域: 

i. 黄色,能直接求出来,就是 sum[row1 - 1, col1 - 1] (为什么减一?因为要剔除掉 row 这一行和 col 这一列)

ii. 绿色,直接求不好求,但是和黄色拼起来,正好是 sum 表内 sum[row1 - 1][col2]的数据;

iii. 同理,蓝色不好求,但是 蓝 + 黄 = sum[row2][col1 - 1] ;

iv. 再看看整个面积,好求嘛?非常好求,正好是 sum[row2][col2] ;

v. 那么,红色就 = 整个面积 - 黄 - 绿 - 蓝,但是绿蓝不好求,我们可以这样减:整个面积 -(绿 + 黄 )-(蓝 + 黄),这样相当于多减去了⼀个黄,再加上即可。

综上所述:红 = 整个面积 - (绿 + 黄)- (蓝 + 黄)+ 黄,从而可得红色区域内的元素总和为:

 sum[row2][col2] - sum[row2][col1 - 1] - sum[row1 - 1][col2] + sum[row1 - 1][col1 - 1]

🍃算法代码:

#include <iostream>
#include <vector>using namespace std;int main() 
{//1.读入数据int n = 0, m = 0, q = 0;cin >> n >> m >> q;vector<vector<int>> arr(n + 1, vector<int>(m + 1));for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> arr[i][j];}}// 2.预处理前缀和矩阵vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));// 防止溢出for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];}}// 3.使用前缀和矩阵int x1 = 0, y1 = 0, x2 = 0, y2 = 0;while(q--){cin >> x1 >> y1 >> x2 >> y2;cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;}return 0;
}

三、寻找数组的中心下标

1.题目链接:724. 寻找数组的中心下标

2.题目描述:

给你一个整数数组 nums ,请计算数组的 中心下标 

数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1 。

示例 1:

输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。

示例 2:

输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。

示例 3:

输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0 。
左侧数之和 sum = 0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

3.解法(前缀和

🍒算法思路:

从中心下标的定义可知,除中心下标的元素外,该元素左边的「前缀和」等于该元素右边的「后缀和」。

  • 因此,我们可以先预处理出来两个数组,一个表示前缀和,另一个表示后缀和。
  • 然后,我们可以用一个 for 循环枚举可能的中心下标,判断每一个位置的「前缀和」以及「后缀和」,如果二者相等,就返回当前下标。

🍒算法代码:

class Solution 
{
public:int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> f(n), g(n);// 预处理前缀和数组和后缀和数组for(int i = 1; i < n; i++){f[i] = f [i - 1] + nums[i - 1];}for(int i = n - 2; i >= 0; i--){g[i] = g[i + 1] + nums[i + 1];}// 使用for(int i = 0; i < n; i++){if(f[i] == g[i])return i;}return -1;}
};

四、除自身以外数组的乘积

1.题目链接:238. 除自身以外数组的乘积

2.题目描述:

给你一个整数数组 nums,返回数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法,且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示:

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

3.解法(前缀和

🍒算法思路:

注意题目的要求,不能使用除法,并且要在 O(N) 的时间复杂度内完成该题。那么我们就不能使用暴力的解法,以及求出整个数组的乘积,然后除以单个元素的方法。

继续分析,根据题意,对于每一个位置的最终结果 ret[i] ,它是由两部分组成的:

  1. nums[0] * nums[1] * nums[2] * ... * nums[i - 1]
  2. nums[i + 1] * nums[i + 2] * ... * nums[n - 1]

于是,我们可以利用前缀和的思想,使用两个数组 post 和 suf,分别处理出来两个信息:

  1. post 表示:i 位置之前的所有元素,即 [0, i - 1] 区间内所有元素的前缀乘积,
  2. suf 表示 i 位置之后的所有元素,即 [i + 1, n - 1] 区间内所有元素的后缀乘积。

然后再处理最终结果。

🍒算法代码:

class Solution 
{
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n), g(n);// 预处理前缀积数组以及后缀积数组f[0] = g[n - 1] = 1;// 处理细节问题for(int i = 1; i < n; i++){f[i] = f[i - 1] * nums[i - 1];}for(int i = n - 2; i >= 0; i--){g[i] = g[i + 1] * nums[i + 1];}// 使用vector<int> ret(n);for(int i = 0; i < n; i++){ret[i] = f[i] * g[i];}return ret;}
};

http://www.ppmy.cn/news/1501286.html

相关文章

深入解读 | Spring Boot中的Maven依赖管理

Maven依赖管理 大家好&#xff0c;今天我们来聊聊Spring Boot中的Maven依赖管理。无论是初学者还是有经验的开发者&#xff0c;理解和掌握Maven依赖管理对于使用Spring Boot开发高效、稳定的应用程序至关重要。在这篇文章中&#xff0c;我们将详细解读Spring Boot中的Maven依赖…

新手vue学习问题汇总(自用)(长期更新)

1.export default export default 是 ES6 模块语法&#xff0c;用于导出模块的默认成员。在 Vue.js 中&#xff0c;通常用来导出一个组件对象&#xff0c;使其可以在其他文件中被导入并使用。 2.props props 是组件接收外部数据的方式。父组件可以通过向子组件传递 props 来…

Oracle自动统计信息收集问题排查脚本

Oracle自动统计信息收集问题排查脚本 检查近期的统计信息自动收集情况: set lines 300 col client_name for a50 col window_name for a30 col job_name for a40 col job_start_time for a60 col job_duration for a50 col window_start_time for a40 col window_end_time fo…

Github 2024-07-25 Go开源项目日报 Top10

根据Github Trendings的统计,今日(2024-07-25统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Go项目10Testify - Go代码测试工具包 创建周期:4237 天开发语言:Go协议类型:MIT LicenseStar数量:22206 个Fork数量:1550 次关注人数:222…

基于微信小程序+SpringBoot+Vue的流浪动物救助(带1w+文档)

基于微信小程序SpringBootVue的流浪动物救助(带1w文档) 基于微信小程序SpringBootVue的流浪动物救助(带1w文档) 本系统实现的目标是使爱心人士都可以加入到流浪动物的救助工作中来。考虑到救助流浪动物的爱心人士文化水平不齐&#xff0c;所以本系统在设计时采用操作简单、界面…

视觉巡线小车(STM32+OpenMV)——总结

文章目录 目录 文章目录 前言 一、效果展示 二、完整流程 1、STM32CubeMX配置 2、Keil编辑 3、硬件接线 4、参数调试 5、图像处理调试 三、总结 前言 基于前面的系列文章&#xff0c;已基本介绍完了基于STM32OpenMV的视觉巡线小车&#xff0c;本文将以小编自己的小车…

creality ender2的3D打印经验教训

创想云-3D打印模型库-一体化3D打印平台 1.开机后要放一张白纸进行检查&#xff0c;看看打印头立平台的距离&#xff0c;如果太近&#xff0c;会灼烧平台&#xff0c;会造成下面的结果&#xff1a; 2.下载模型&#xff0c;可以在线切片&#xff0c;要看看是否要支撑 没有支撑可…

Java聚合快递小程序对接云洋系统程序app源码

​一场物流效率的革命 引言&#xff1a;物流新时代的序章 在数字化浪潮席卷各行各业的今天&#xff0c;物流行业也迎来了前所未有的变革。为了进一步提升物流效率&#xff0c;优化用户体验&#xff0c;聚合快递系统与云洋系统小程序的对接成为了行业内外关注的焦点。这一创新…