网站开发模块,钟楼区建设局网站,构建网站的安全,想注册自己的品牌怎么注册送给大家一句话#xff1a; 既然已经做出了选择#xff0c;最好还是先假定自己是对的。焦虑未来和后悔过去#xff0c;只经历一个就够了。 – 张寒寺 《不正常人类症候群》
☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆ ☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆ ☆ミヾ(∇≦((ヾ…
送给大家一句话 既然已经做出了选择最好还是先假定自己是对的。焦虑未来和后悔过去只经历一个就够了。 – 张寒寺 《不正常人类症候群》
☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆ ☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆ ☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆ 前缀和入门 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 算法步骤
初始化前缀和数组创建一个新数组 dp,一般多开一位。计算前缀和遍历原数组 A根据题目更新状态。查询区间和更加区间得到答案。
1.2 使用场景
频繁区间和查询当需要对一个数组进行多次区间和查询时前缀和可以大幅提高查询效率。动态数据更新在某些情况下数组中的元素可能会动态更新前缀和也能有效处理这种情况下的区间和查询。多维数组处理前缀和可以扩展到多维数组用于处理多维数据区间和的问题。
1.3 时间复杂度分析
预处理时间复杂度O(n)其中 n 是原数组 A 的长度。查询时间复杂度O(1)对于每次区间和查询。
1.4 空间复杂度分析
空间复杂度O(n)用于存储前缀和数组 dp。
前缀和算法在处理数组区间和问题时非常高效适用于需要频繁查询和高效处理大量数据的场景。通过前缀和的预处理可以显著减少计算成本提高程序的运行效率也就是 空间换时间。
2 牛客 DP35 【模板】二维前缀和
上链接 DP34 一维前缀和
题目描述 根据题目描述我们大概知道我们是求一个区间上的和。题目很好理解奥接下来我们就来通过这道题来入门前缀和算法
算法思路
首先最好想的就是暴力算法求指定区间的和那么直接暴力求不就可以了但是毋庸置疑的是这样一定一定会超时毕竟是O(n^2)的暴力算法。
那么来看前缀和算法这是一个解决这个问题的优秀算法。前缀和的思想很简单就是对数组进行一遍预处理得到每个数组位置之前所有数的和然后在通过减法求得数据。
创建一个大小为 n 1 的数组大小为 n 1可以避免一些边界情况从 下标 1 开始读入数据创建一个大小为 n 1 的 dp 数组从 下标 1 开始预处理数据得到答案
#include iostream
#include vector
using namespace std;int main() {int n , q;cin n q;//读入数据vectorlong long nums(n 1);for(int i 1 ; i n 1 ; i ){cin nums[i];}//预处理数据vectorlong 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)的暴力算法啊。
那么来看前缀和算法这是一个解决这个问题的优秀算法。前缀和的思想很简单就是对数组进行一遍预处理得到每个数组位置之前所有数的和然后在通过减法求得数据。
创建一个大小为 (n 1) *( n 1) 的矩阵大小为 n 1可以避免一些边界情况从 坐标1,1 开始读入数据创建一个大小为 (n 1) *( n 1) 的 dp 矩阵从 坐标1,1开始预处理数据得到答案
这里的预处理就有说法了这和线性的数组不一样我们做一个图就可以很好理解预处理然后进行 求(ij)的矩阵和 可以理解为(i-1j)的矩阵和 加上 (ij-1)的矩阵和加上i,j的值再减去(i-1j-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;//创建二维数组 匿名对象构造vectorvectorint nums(n 1 , vectorint(m 1));for(int i 1 ; i n ; i )for(int j 1 ; j m ; j)cinnums[i][j];//进行前缀和计算vectorvectorint dp(n 1 , vectorint(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(vectorint nums) {//预处理vectorint 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)的算法 那么如何进行呢?
很简单我们在创建一个前缀乘积数组与一个后缀乘积数组分开进行预处理即可。然后按照对应位置通过n - 1 的前缀乘积与 n 1 的后缀乘积相乘 得到 除自身以外数组的乘积就可以了。
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint dpfront(n 1);vectorint 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♪(ω)谢谢阅读
下一篇文章见
