【刷题】前缀和入门

embedded/2024/9/22 15:34:32/

在这里插入图片描述

送给大家一句话:
既然已经做出了选择,最好还是先假定自己是对的。焦虑未来和后悔过去,只经历一个就够了。 – 张寒寺 《不正常人类症候群》

☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆
☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆
☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆


前缀和入门

  • 1 前言
    • 1.1 算法步骤
    • 1.2 使用场景
    • 1.3 时间复杂度分析
    • 1.4 空间复杂度分析
  • 2 牛客 DP35 【模板】二维前缀和
  • 3 牛客 DP35 【模板】二维前缀和
  • Leetcode 724. 寻找数组的中心下标
  • Leetcode 238. 除自身以外数组的乘积
  • Thanks♪(・ω・)ノ谢谢阅读!!!
  • 下一篇文章见!!!

1 前言

今天我学习了一个新算法:前缀和算法
前缀和算法是一种高效处理数组区间和查询问题的算法。它的核心思想是在 O(n) 的时间复杂度内对输入数组进行预处理,从而使得后续每次查询数组中任意区间内元素和的时间复杂度降低到 O(1)。

1.1 算法步骤

  1. 初始化前缀和数组:创建一个新数组 dp,一般多开一位。
  2. 计算前缀和:遍历原数组 A,根据题目更新状态。
  3. 查询区间和:更加区间得到答案。

1.2 使用场景

  1. 频繁区间和查询:当需要对一个数组进行多次区间和查询时,前缀和可以大幅提高查询效率。
  2. 动态数据更新:在某些情况下,数组中的元素可能会动态更新,前缀和也能有效处理这种情况下的区间和查询。
  3. 多维数组处理:前缀和可以扩展到多维数组,用于处理多维数据区间和的问题。

1.3 时间复杂度分析

  • 预处理时间复杂度:O(n),其中 n 是原数组 A 的长度。
  • 查询时间复杂度:O(1),对于每次区间和查询。

1.4 空间复杂度分析

  • 空间复杂度:O(n),用于存储前缀和数组 dp。

前缀和算法在处理数组区间和问题时非常高效,适用于需要频繁查询和高效处理大量数据的场景。通过前缀和的预处理,可以显著减少计算成本,提高程序的运行效率,也就是 空间换时间

2 牛客 DP35 【模板】二维前缀和

上链接!!! DP34 一维前缀和

题目描述

在这里插入图片描述
根据题目描述,我们大概知道我们是求一个区间上的和。题目很好理解奥,接下来我们就来通过这道题来入门前缀和算法!!!

算法思路

首先最好想的就是暴力算法,求指定区间的和那么直接暴力求不就可以了?!但是毋庸置疑的是这样一定一定会超时,毕竟是O(n^2)的暴力算法

那么来看前缀和算法,这是一个解决这个问题的优秀算法。前缀和的思想很简单,就是对数组进行一遍预处理,得到每个数组位置之前所有数的和,然后在通过减法求得数据。

  1. 创建一个大小为 n + 1 的数组(大小为 n + 1可以避免一些边界情况)
  2. 从 下标 1 开始读入数据
  3. 创建一个大小为 n + 1 的 dp 数组
  4. 从 下标 1 开始预处理数据
  5. 得到答案
#include <iostream>
#include <vector>
using namespace std;int main() {int n , q;cin >> n >> q;//读入数据vector<long long > nums(n + 1);for(int i = 1 ; i < n + 1 ; i++ ){cin >> nums[i];}//预处理数据vector<long long > sum(n + 1);for(int i = 1 ;  i < nums.size() ;i++ ){//i 位置的和等于 i - 1 位置的和 加上 i 位置的值//如果数组大小为n 那 i 从 0开始 那么就会读入 nums[-1]就会报错sum[i] = sum[i - 1] + nums[i];}//得出结果while(q--){int n1 , n2;cin >> n1 >> n2;cout <<sum[n2] - sum[n1 - 1] << endl;}return 0;
}

这样提交:过啦!!!
这里有点像动态规划

3 牛客 DP35 【模板】二维前缀和

家人们跟上节奏!!!DP35 二维前缀和

题目描述

在这里插入图片描述

根据题目描述,这道题是刚才一维的升级版,我们需要计算一个指定矩阵的和。那么依然使用的是前缀和来进行预处理。这道题就要注意细节处理了

算法思路

首先最好想的就是暴力算法,求指定矩阵的和那么直接暴力求不就可以了?!但是毋庸置疑的是这样一定一定会超时,O(n^3)的暴力算法啊。

那么来看前缀和算法,这是一个解决这个问题的优秀算法。前缀和的思想很简单,就是对数组进行一遍预处理,得到每个数组位置之前所有数的和,然后在通过减法求得数据。

  1. 创建一个大小为 (n + 1) *( n + 1) 的矩阵(大小为 n + 1可以避免一些边界情况)
  2. 从 坐标(1,1) 开始读入数据
  3. 创建一个大小为 (n + 1) *( n + 1) 的 dp 矩阵
  4. 从 坐标(1,1)开始预处理数据
  5. 得到答案

这里的预处理就有说法了,这和线性的数组不一样,我们做一个图就可以很好理解预处理然后进行:
求(i,j)的矩阵和:
可以理解为(i-1,j)的矩阵和 加上 (i,j-1)的矩阵和,加上(i,j)的值再减去(i-1,j-1)的矩阵和(因为多加了一遍)
在这里插入图片描述
这样就可以进行预处理了:
然后我们还需要如何得到答案:
在这里插入图片描述
我们想要求以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和。
可以通过 (x2,y2) 矩阵和 减去(x2 , y1 - 1)矩阵和 减去(x1 - 1 , y2)矩阵和 加上(x1 - 1, y1 - 1)的矩阵和(因为多减了一遍)

#include <iostream>
#include <vector>
#define int long longusing namespace std;signed main() {int n , m ,q;cin >> n >> m >> q;//创建二维数组 匿名对象构造vector<vector<int>> nums(n + 1 , vector<int>(m + 1));for(int i = 1 ; i <= n ; i++ )for(int j = 1 ; j <= m ; j++)cin>>nums[i][j];//进行前缀和计算vector<vector<int>> dp(n + 1 , vector<int>(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] - dp[i-1][j-1] + nums[i][j];int x1 , x2 , y1 ,y2;while(q--){cin >> x1 >> y1 >> x2 >>y2;cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << endl;}return 0;
}

提交过啦!!!

Leetcode 724. 寻找数组的中心下标

跟上节奏:724. 寻找数组的中心下标

题目描述

在这里插入图片描述
这道题可谓是一维前缀和的变形了,我们来秒杀这个题目

算法思路

我们先进行一下前缀和的预处理,然后根据条件判断即可:

class Solution {
public:int pivotIndex(vector<int>& nums) {//预处理vector<int> dp(nums.size() + 1);for(int i = 1 ; i <= nums.size() ;i++){dp[i] = dp[i - 1] + nums[i - 1];}int ans = -1;//根据题目要求求得即可for(int i = 0 ; i < nums.size() ;i++){if(dp[i] == dp[nums.size()] - dp [i + 1] ){ans = i ;break;}}return ans;}
};

提交过啦!!!

Leetcode 238. 除自身以外数组的乘积

最后一道:238. 除自身以外数组的乘积

题目描述

在这里插入图片描述
注意到题目要求,我们看来是要使用前缀和来解决问题了。

算法思路

这道题的难点在于不能不能使用除法,而且还要进行O(n)的算法
那么如何进行呢???

  1. 很简单,我们在创建一个前缀乘积数组与一个后缀乘积数组,分开进行预处理即可。
  2. 然后按照对应位置,通过n - 1 的前缀乘积与 n + 1 的后缀乘积相乘 得到 除自身以外数组的乘积,就可以了。
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> dpfront(n + 1);vector<int> dpback(n + 1);//细节处理,不能为0哦!!!dpfront[0] = 1;dpback[n]  = 1;//预处理for(int i = 1 ; i <= n ; i++){   //一次处理两个数组,提高效率dpfront[i] = dpfront[i - 1] * nums[i - 1];dpback[n - i] = dpback[n - i + 1] * nums[n - i];}//得到答案for(int i = 0 ; i < n ; i++){nums[i] = dpfront[i] * dpback[i + 1];}return nums;}
};

提交:过啦!!!

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!


http://www.ppmy.cn/embedded/11742.html

相关文章

python基础知识三(运算符、while循环、for循环)

目录 运算符&#xff1a; 算术运算符&#xff1a; 比较运算符&#xff1a; 赋值运算符&#xff1a; 逻辑运算符&#xff1a; 位运算符&#xff1a; 成员运算符&#xff1a; while循环&#xff1a; 1. while循环的语法&#xff1a; 2. while循环的执行过程&#xff1a…

第26天:安全开发-PHP应用模版引用Smarty渲染MVC模型数据联动RCE安全

第二十六天 一、PHP新闻显示-数据库操作读取显示 1.新闻列表 数据库创建新闻存储代码连接数据库读取页面进行自定义显示 二、PHP模版引用-自写模版&Smarty渲染 1.自写模版引用 页面显示样式编排显示数据插入页面引用模版调用触发 2.Smarty模版引用 1.下载&#xff1a…

1016 部分A+B

正整数 A 的“DA​&#xff08;为 1 位整数&#xff09;部分”定义为由 A 中所有 DA​ 组成的新整数 PA​。例如&#xff1a;给定 A3862767&#xff0c;DA​6&#xff0c;则 A 的“6 部分”PA​ 是 66&#xff0c;因为 A 中有 2 个 6。 现给定 A、DA​、B、DB​&#xff0c;请…

2024-04-22(AJAX)

1.什么是Ajax 使用浏览器的XMLHttpRequest对象和服务器进行通信 浏览器网页中&#xff0c;使用Ajax技术&#xff08;XMLHttpRequest对象&#xff09;发起获取服务器数据的请求&#xff0c;服务器将数据给前端&#xff0c;前端拿到数据后&#xff0c;展示到网页。 2.为什么学…

Three.js 入门——核心概念和坐标系理解

Three.js 是什么&#xff1f; 一个封装了 WebGL 的库&#xff0c;简化 WebGL 的使用 WebGL vs OpenGL OpenGL 主要被认为是一种 API&#xff08;应用程序编程接口&#xff09;&#xff0c;它为我们提供了大量可用于操作图形和图像的函数&#xff0c;主要用 C语言编写的。 然…

setTimeout运行机制

当调用 setTimeout 函数时&#xff0c;它用于安排在一定延迟后执行的代码块。它的运行机制如下&#xff1a; 调度任务&#xff1a; 当调用 setTimeout 时&#xff0c;JavaScript 引擎会创建一个定时器&#xff0c;并将指定的代码块&#xff08;回调函数&#xff09;添加到一个称…

控制台居然可以这么玩?五分钟带你上手ANSI指令,实现一个log工具包

目录 前言 基础知识 进阶实践 ANSI参数 ANSI类 JSLog类 工具的使用说明 配置相关 全局配置项 默认配置 基本用法 打印字符 添加全局配置项 清空所有样式及操作行为 校验传入的参数是否正确 样式控制 Node环境 浏览器中 光标控制指令 光标位置偏移 滚动条控…

CentOS系统上经常使用的一些基本命令

CentOS是一种流行的Linux发行版&#xff0c;常见的命令包括&#xff1a; 文件和目录操作&#xff1a; ls: 列出目录内容。cd: 切换目录。pwd: 显示当前工作目录。mkdir: 创建新目录。rm: 删除文件或目录。cp: 复制文件或目录。mv: 移动文件或目录。 文件查看和编辑&#xff1a…