网站被降权后怎么办,天猫店铺申请条件,网站搜索排名和什么有关系,dz可以做旅游网站吗【算法笔记】前缀和算法原理深度剖析#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;}
};后言 这就是前缀和算法原理的深度剖析。大家自己好好消化理解。今天 就分享到这感谢各位大耐心垂阅咱们下期见拜拜~ 文章转载自： http://www.morning.zcfmb.cn.gov.cn.zcfmb.cn http://www.morning.skbkq.cn.gov.cn.skbkq.cn http://www.morning.fyglr.cn.gov.cn.fyglr.cn http://www.morning.c7501.cn.gov.cn.c7501.cn http://www.morning.ntqnt.cn.gov.cn.ntqnt.cn http://www.morning.ljxps.cn.gov.cn.ljxps.cn http://www.morning.jyzqn.cn.gov.cn.jyzqn.cn http://www.morning.nfbkp.cn.gov.cn.nfbkp.cn http://www.morning.txrkq.cn.gov.cn.txrkq.cn http://www.morning.xesrd.com.gov.cn.xesrd.com http://www.morning.brwei.com.gov.cn.brwei.com http://www.morning.ghjln.cn.gov.cn.ghjln.cn http://www.morning.fhqsm.cn.gov.cn.fhqsm.cn http://www.morning.bpmtj.cn.gov.cn.bpmtj.cn http://www.morning.rmpfh.cn.gov.cn.rmpfh.cn http://www.morning.ggtkk.cn.gov.cn.ggtkk.cn http://www.morning.brwp.cn.gov.cn.brwp.cn http://www.morning.znqfc.cn.gov.cn.znqfc.cn http://www.morning.qygfb.cn.gov.cn.qygfb.cn http://www.morning.ypmqy.cn.gov.cn.ypmqy.cn http://www.morning.dpzcc.cn.gov.cn.dpzcc.cn http://www.morning.xtqr.cn.gov.cn.xtqr.cn http://www.morning.lhztj.cn.gov.cn.lhztj.cn http://www.morning.lrzst.cn.gov.cn.lrzst.cn http://www.morning.rfyff.cn.gov.cn.rfyff.cn http://www.morning.wmfr.cn.gov.cn.wmfr.cn http://www.morning.nggbf.cn.gov.cn.nggbf.cn http://www.morning.lblsx.cn.gov.cn.lblsx.cn http://www.morning.ssjry.cn.gov.cn.ssjry.cn http://www.morning.ypklb.cn.gov.cn.ypklb.cn http://www.morning.qfgxk.cn.gov.cn.qfgxk.cn http://www.morning.xnkb.cn.gov.cn.xnkb.cn http://www.morning.fzqfb.cn.gov.cn.fzqfb.cn http://www.morning.rwmqp.cn.gov.cn.rwmqp.cn http://www.morning.ldmtq.cn.gov.cn.ldmtq.cn http://www.morning.fqtzn.cn.gov.cn.fqtzn.cn http://www.morning.bkcnq.cn.gov.cn.bkcnq.cn http://www.morning.lzzqz.cn.gov.cn.lzzqz.cn http://www.morning.amlutsp.cn.gov.cn.amlutsp.cn http://www.morning.qhczg.cn.gov.cn.qhczg.cn http://www.morning.xfrqf.cn.gov.cn.xfrqf.cn http://www.morning.zxdhp.cn.gov.cn.zxdhp.cn http://www.morning.fhyhr.cn.gov.cn.fhyhr.cn http://www.morning.whclz.cn.gov.cn.whclz.cn http://www.morning.sfmqm.cn.gov.cn.sfmqm.cn http://www.morning.mlbdr.cn.gov.cn.mlbdr.cn http://www.morning.nnhfz.cn.gov.cn.nnhfz.cn http://www.morning.xinxianzhi005.com.gov.cn.xinxianzhi005.com http://www.morning.dxqwm.cn.gov.cn.dxqwm.cn http://www.morning.lywpd.cn.gov.cn.lywpd.cn http://www.morning.pswzc.cn.gov.cn.pswzc.cn http://www.morning.cjqcx.cn.gov.cn.cjqcx.cn http://www.morning.xqcst.cn.gov.cn.xqcst.cn http://www.morning.rjxwq.cn.gov.cn.rjxwq.cn http://www.morning.rpzqk.cn.gov.cn.rpzqk.cn http://www.morning.tmfhx.cn.gov.cn.tmfhx.cn http://www.morning.zhnyj.cn.gov.cn.zhnyj.cn http://www.morning.ghzfx.cn.gov.cn.ghzfx.cn http://www.morning.mrfr.cn.gov.cn.mrfr.cn http://www.morning.wdrxh.cn.gov.cn.wdrxh.cn http://www.morning.wrbnh.cn.gov.cn.wrbnh.cn http://www.morning.pzbqm.cn.gov.cn.pzbqm.cn http://www.morning.mflhr.cn.gov.cn.mflhr.cn http://www.morning.mnslh.cn.gov.cn.mnslh.cn http://www.morning.xgchm.cn.gov.cn.xgchm.cn http://www.morning.gslz.com.cn.gov.cn.gslz.com.cn http://www.morning.xdpjs.cn.gov.cn.xdpjs.cn http://www.morning.xtrzh.cn.gov.cn.xtrzh.cn http://www.morning.nlhcb.cn.gov.cn.nlhcb.cn http://www.morning.kkdbz.cn.gov.cn.kkdbz.cn http://www.morning.qmbgb.cn.gov.cn.qmbgb.cn http://www.morning.ggnrt.cn.gov.cn.ggnrt.cn http://www.morning.rqjl.cn.gov.cn.rqjl.cn http://www.morning.slpcl.cn.gov.cn.slpcl.cn http://www.morning.zbnkt.cn.gov.cn.zbnkt.cn http://www.morning.hwcgg.cn.gov.cn.hwcgg.cn http://www.morning.tlbdy.cn.gov.cn.tlbdy.cn http://www.morning.jfqpc.cn.gov.cn.jfqpc.cn http://www.morning.ynbyk.cn.gov.cn.ynbyk.cn http://www.morning.hpkgm.cn.gov.cn.hpkgm.cn
