商城网站建设网络公司,自己公司网站如何添加qq,dedecms模板安装,土木英才网招聘信息【算法笔记】前缀和算法原理深度剖析#xff08;超全详细版#xff09; #x1f525;个人主页#xff1a;大白的编程日记
#x1f525;专栏#xff1a;算法笔记 文章目录 【算法笔记】前缀和算法原理深度剖析#xff08;超全详细版#xff09;前言一.一维前缀和1.1题…
【算法笔记】前缀和算法原理深度剖析超全详细版 个人主页大白的编程日记
专栏算法笔记 文章目录 【算法笔记】前缀和算法原理深度剖析超全详细版前言一.一维前缀和1.1题目1.2算法原理解析1.3代码实现 二.二维前缀和2.1题目2.2算法原理解析2.3下标映射2.4初始化问题2.5代码实现 三.寻找数组的中心下标3.1题目3.2思路分析3.3代码实现 四.除自身以外数组的乘积4.1题目4.2思路分析4.3总结4.4代码实现 五.和为k的子数组5.1题目5.2思路分析5.3代码实现 六.和可被k整除的子数组6.1题目6.4思路分析6.3代码实现 七.连续数组7.1题目7.1思路分析7.3代码实现 八.矩阵区域和8.1题目8.2思路分析8.3代码实现 后言 前言 哈喽各位小伙伴大家好上期我们讲了二分算法。今天我们来讲前缀和的算法原理。话不多说咱们进入正题向大厂冲锋 一.一维前缀和
1.1题目
题目:【模板】前缀和
1.2算法原理解析
我们根据前缀和算法就可以快速求出区间和。
为了防止越界我们要让前缀和数组下标从1开始。
1.3代码实现
#include iostream
#includevector
using namespace std;
int main()
{int n,q;cinnq;vectorlong long dp(n1);//多开一个节点防止越界int tmp0;for(int i1;in;i){cindp[i];}for(int i1;in;i){dp[i]dp[i-1];}int l,r;while(q--){cinlr;coutdp[r]-dp[l-1]endl;}
}
// 64 位输出请用 printf(%lld)二.二维前缀和
2.1题目
题目:二维前缀和 2.2算法原理解析 2.3下标映射 2.4初始化问题
如果用到两个前缀和区间求某区间的和 我们初始化的值并不重要。
验证
2.5代码实现
#include iostream
#includevector
using namespace std;int main()
{int n, m, q;cin n m q;vectorvectorlong long arr(n,vectorlong long(m));for (int i 0; i n; i){for (int j 0; j m; j){cin arr[i][j];}}vectorvectorlong long dp(n1,vectorlong long(m 1));for (int i 1; i n; i){for (int j 1; j m; j){dp[i][j] dp[i][j - 1]dp[i-1][j]-dp[i-1][j-1]arr[i-1][j-1];}}while (q--){int x1, y1, x2, y2;cin x1 y1 x2 y2;long long sum0;sumdp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]dp[x1-1][y1-1];coutsumendl;}
}三.寻找数组的中心下标
3.1题目
题目寻找数组的中心下标
3.2思路分析
这里我们借助前缀和数组和后缀和数组即可快速判断中心下标。
3.3代码实现
class Solution {
public:int pivotIndex(vectorint nums){int nnums.size();vectorint f(n),g(n);for(int i1;in;i)//前缀和数组{f[i]nums[i-1]f[i-1];}for(int in-2;i0;i--)//后缀和数组{g[i]g[i1]nums[i1];}for(int i0;in;i)//判断{if(f[i]g[i]){return i;}}return -1;}
};四.除自身以外数组的乘积
4.1题目
题目除自身以外数组的乘积
4.2思路分析 4.3总结 4.4代码实现
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int nnums.size();vectorint f(n),g(n),ret(n);f[0]g[n-1]1;for(int i1;in;i)//前缀和数组{f[i]f[i-1]*nums[i-1];}for(int in-2;i0;i--)//后缀和数组{g[i]g[i1]*nums[i1];}for(int i0;in;i){ret[i]f[i]*g[i];}return ret;}
};五.和为k的子数组
5.1题目
题目和为k的子数组
5.2思路分析 5.3代码实现
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,int hash;hash[0]1;//整个区间和为kint sum0,ret0;for(auto e:nums){sume;//计算前缀和if(hash.count(sum-k))//统计和为sum-k区间个数{rethash[sum-k];}hash[sum];//填入前缀和信息}return ret;}
};六.和可被k整除的子数组
6.1题目
题目和可被k整除的子数组
6.4思路分析 6.3代码实现
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,int hash;hash[0]1;//整个区间和为kint sum0,ret0;for(auto e:nums){sume;//计算前缀和if(hash.count((sum%kk)%k))//统计和为被k整除区间个数负数修正{rethash[(sum%kk)%k];}hash[(sum%kk)%k];//填入前缀和%k信息}//(a-b)%pa%pb%p同余定理return ret;}
};七.连续数组
7.1题目
题目连续数组
7.1思路分析 7.3代码实现
class Solution {
public:int findMaxLength(vectorint nums){unordered_mapint,int hash;hash[0]-1;int sum0,len0;for(int i0;inums.size();i){sum(nums[i]0?-1:1);//0就变成-1if(hash.count(sum-0)){lenmax(len,i-hash[sum]);//更新长度}else//相同的前缀和不更新{hash[sum]i;//更新哈希表前缀和信息}}return len;}
};八.矩阵区域和
8.1题目
题目矩阵区域和
8.2思路分析 8.3代码实现
class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k){int mmat.size(),nmat[0].size();vectorvectorint arr(m1,vectorint(n1));for(int i1;im1;i)//处理前缀和数组{for(int j1;jn1;j){arr[i][j]arr[i][j-1]arr[i-1][j]-arr[i-1][j-1]mat[i-1][j-1];}}vectorvectorint arr1(m,vectorint(n));for(int i0;im;i){for(int j0;jn;j){int x1max(0,i-k)1;int x2min(m-1,ik)1;int y1max(0,j-k)1;int y2min(n-1,jk)1;//计算下标 1映射dp数组arr1[i][j]arr[x2][y2]-arr[x2][y1-1]-arr[x1-1][y2]arr[x1-1][y1-1];}}return arr1;}
};后言 这就是前缀和算法原理的深度剖析。大家自己好好消化理解。今天 就分享到这感谢各位大耐心垂阅咱们下期见拜拜~
