本机网站环境搭建,比较出名的网站建设公司,网站产品介绍页面的布局方案,wordpress语音问答目录
一、【模版】前缀和
参考代码#xff1a;
二、【模版】 二维前缀和
参考代码#xff1a;
三、寻找数组的中心下标
参考代码#xff1a;
四、除自身以外数组的乘积
参考代码#xff1a;
五、和为K的子数组
参考代码#xff1a;
六、和可被K整除的子数组
参…目录
一、【模版】前缀和
参考代码
二、【模版】 二维前缀和
参考代码
三、寻找数组的中心下标
参考代码
四、除自身以外数组的乘积
参考代码
五、和为K的子数组
参考代码
六、和可被K整除的子数组
参考代码
七、连续数组
参考代码
八、矩阵区域和
参考代码
总结 一、【模版】前缀和
【模版】前缀和
题目描述 数组的元素是从标为1开始的n是数组的个数q是查询的次数查询l到r这段区间的和。 解法一暴力解法直接查找l到r这段区间之和但是效率太低查询q次每次遍历一遍数组时间复杂度O(q*N)n和q的数据范围是1到10^5暴力解法过不了。 解法二前缀和快速求出数组中某一个连续区间的和时间复杂度O(q)O(N)
第一步预处理出来一个前缀和数组我们要要求1到3的和我们用dp[i-1]arr[i]就是1到3的和了。
dp[i]表示表示[1,i]区间内所有元素的和。
dp[i] dp[i-1] arr[i] 第二步使用前缀和数组
如下比如我们要查找l~r这段区间的和那么我们直接去dp数组取出下标为r的这个元素此元素就是1~r的之和我们减去l-1得到的就是l~r这段区间之和。 这里还有一个问题就是为什么下标要从1开始计数为了处理边界情况
初始化添加虚拟结点辅助结点 参考代码
#include iostream
#include vector
using namespace std;int main()
{//1.读入数据int n,q;cinnq;vectorintarr(n1);for(int i 1;i n;i) cinarr[i];//2.预处理出来一个前缀和数组vectorlong longdp(n1); //防止溢出for(int i 0;in;i) dp[i] dp[i-1] arr[i];//3.使用前缀和数组int l,r;while(q--){cinlr;coutdp[r] -dp[l-1]endl;}} 时间复杂度O(q)O(n) 二、【模版】 二维前缀和
题目链接二维前缀和
题目描述 题目解析
1.从第一行第一列开始到第二列到二行二列。如下
2.从第一行第一列开始到第三列到三行三列。
3.从第一行第二列开始到4列到三行四列。 算法原理
解法一暴力解法,模拟让我求哪段区间我就加到哪段区间如下比如让我们全部求出来那就从头加到尾时间复杂度高这道题过不了因为时间复杂度为O(n*m*q) 解法二前缀和
1.预处理出来一个前缀和矩阵
dp[i][j]表示从[1,1]位置到[i,j]位置这段区间里面所有元素和。
如下图我们把它抽象出来这里我们分为四块面积分别为A、B、C、D我们要求得dp[i][j]这段区间的和我们ABCD就等于dp[i][j]我们求B和C这段区间的和是不太好求的所以我们这样求(AB) (A C) D - A这里减A是因为多算了一个A所以要减掉AB这段区间的值非常好求就是dp[i-1][j]这个位置AC就是dp[i][j-1]再加上D这个位置的值就是数组里面的arr[i][j]减去A也就是dp[i-1][j-1]这样就推出了我们预处理的公式。如下图 2.使用前缀和矩阵
如下假如我们要求D这段区间的和那么我们又被分成了四个部分竟然要求D这段区间的和我们就ABCD求得结果之后我们先减去上面这部分就是AB这部分因为AB这部分可以直接算出了也就是下图绿色小方块那个位置在减去AC这部分但是这样我们发现多减了一个A所以我们要加上一个AD ABCD - (AB)-(AC)A(通分之后就等于D)ABCD其实就等于dp[x2][y2]然后减去AB也就是dp[x1 - 1][y2]再减去AC也就是dp[x2][y1-1]在加上A也就是dp[x1-1][y1-1]我们直接套用公式就能用O(1)的时间复杂度得出结果。 参考代码
#include iostream
#include vector
using namespace std;int main()
{//1.读入数据int n 0,m 0,q 0;cinnmq;vectorvectorlong longarr(n1,vectorlong long(m1));for(int i 1;i n;i)for(int j 1;j m ;j)cinarr[i][j];//2.预处理前缀和矩阵vectorvectorlong longdp(n1,vectorlong long(m1));//防止溢出for(int i 1; in; i)for(int j 1; jm ;j)dp[i][j] dp[i-1][j] dp[i][j-1] arr[i][j] - dp[i-1][j-1];//3.使用前缀和矩阵int x10,y10,x20,y20;while(q--){cin x1 y1 x2 y2;coutdp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1]endl;}return 0;} 时间复杂为O(n*m) O(q) 三、寻找数组的中心下标
题目链接寻找数组的中心下标
题目描述 题目解析
如下图两边都等于11那么就返回6的下标如果全是0那么就返回最左边的下标也就是0因为有多个中心下标不存在则返回-1 解法一暴力解法枚举中心下标左边相加的值是否等于右边相加的值每次枚举一次中心下标都要左边相加右边相加枚举下标时间复杂O(N)求和依旧使用O(N)的时间复杂度最终时间复杂度O(N^2)。
解法二前缀和
我们利用前缀和的思想来实现竟然要求某一段区间的和那么前缀和预处理出来的那个数组不就可以我们还要求后面那一段区间的和我们把前缀和改一下改成后缀和就可以了。
我们用f来表示前缀和数组f[i]表示[0,i-1]区间所有元素的和。 f [i] f [i-1] nums[i-1] g后缀和数组g[i]表示[i1,n-1]区间所有元素的和 g [i] g [i1] nums[i1] 最后进行判断枚举所有的中心下标从0~n-1然后判断f[i] g[i]如果有很多中心下标要返回最左边的所以我们枚举所有的中心下标i然后判断f[i] g[i]因为f[i]表示的就是左边所有元素的和g[i]保存的就是右边所有元素的和判断是否相等如果相等返回i不相等继续往后面找找到最后一个位置依旧没找到就返回-1
细节问题
当我们的f等于0的时候我们代入上面发现会越界访问0~-1这里没有元素所以f(0) 0
当g等于n-1的时候我们代入上面也会发生越界访问n-1的右边是没有任何元素的所以g(0) 0
填写元素顺序f表是正着填的从左到右g表是倒着填的从右到左
参考代码
class Solution {
public:int pivotIndex(vectorint nums) {int n nums.size();vectorintf(n),g(n);//1.预处理前缀和数组以及后缀和数组for(int i 1;in;i)f[i] f[i-1] nums[i-1];for(int j n-2;j 0;j--)g[j] g[j 1] nums[j1];//2.使用for(int i 0;in;i){if(f[i] g[i])return i;}return -1;}
}; 时间复杂度O(N) 四、除自身以外数组的乘积
题目链接除自身以外数组的乘积
题目描述 举个例子
除1以为2*3*4等于24除2以外1*3*4等于12除3以为1*2*4等于8除4以为1*2*3等于6题目已经提示我们了使用前缀和 后缀和。 解法一暴力解法
暴力解法其实和我们上面举的例子一样比如我们要求除第一个位置以外的值我们就从头遍历尾要求第二个位置就从第一个开始遍历跳过我们自己然后依次遍历以此类推。
但是时间复杂度太高了O(N^2) 解法二前缀积
本题的思路和上题的思路一样但是有些细节有变化。
1.预处理前缀积以及后缀积 我们不需要i位置的元素只要0~i-1位置的元素即可。表示如下
f表示前缀积f [0,i -1 ] 区间内所有元素的乘积
我们要求i-1位置的乘积的时候我们知道i-2位置的乘积让它乘以i-1位置的值就可以了 f[i] f [i-1] * nums[i-1] 注意我们上面的f [i-1 ]位置是上图i-2的位置因为我们f[i]表示的是i-1位置。
我们知道了i2位置的乘积之后用它乘以i1位置的值即可。
g表示后缀积g[i]表示[i1,n-1] g[i] g[i1] * nums[i1] 2.使用
我们在i这个位置填写数据的时候我们用f[i] * g[i]因为f[i]表示左边的乘积g表示右边的乘积
3.细节问题
当我们i等于0的时候其实会越界访问所以我们需要处理那么我们f(0)给什么值合适上面那道题我们给的是0这道题我们不能给0因为0*nums[i-1]还是0那么会影响我们的结果所以我们要给1,f(0) 1g(n-1) 1
参考代码
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorintf(n,1),g(n,1);vectorint answer(n);//1.预处理前缀积 后缀积for(int i 1;in;i)f[i] f[i-1] * nums[i-1];for(int i n-2;i0;i--)g[i] g[i1] * nums[i1];//2.使用for(int i 0;in;i){answer[i] f[i] * g[i];}return answer;}
}; 时间复杂度O(N) 五、和为K的子数组
题目链接560. 和为 K 的子数组 - 力扣LeetCode
题目描述 前缀和哈希表 以i位置为结尾的所有的子数组在[0,i-1]区间内有多少个前缀和等于sum[i] - k就有多少个和为k的子数组哈希表中分别存储前缀和、次数。 细节问题 1.在计算i位置之前哈希表里面只保存[0,i-1]位置的前缀和 2.不用真的创建一个前缀和数组用一个变量sum来标记前一个位置的前缀和即可 3.如果整个前缀和等于k那么我们需要提前把hash[0] 1。0,1 注意不能使用滑动窗口来做优化(双指针)因为有0和负数如下图这种情况我们left不断向右移动那么有可能中间还有子数组和为 k 参考代码
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,inthash;int sum 0,ret 0;hash[0] 1;for(auto x : nums){sum x;if(hash.count(sum - k)) ret hash[sum - k];hash[sum];}return ret;}
}; 时间复杂度为 O(n)空间复杂度也为 O(n) 六、和可被K整除的子数组
题目链接和可被K整除的子数组
题目描述 补充知识 1.同余定理 (a - b) / p k.....0 a % p b % p 举个例子(26-12) / 7 26 % 7 12 % 7 7 % 2 1 - 7 - 2 5 - 2 3 -2 1 取余数的本质就是你这个数有多少个2的倍数就把2的倍数干掉减到这个数比2小 (12 * 3) % 2 1(相当于有3个2的倍数得出等式(a p * k) % p a % p 证明 (a- b) / p k a - b p * k a b p * k左右相等那么左右%p也相等 a %p (b p * k) % p b % pp * k有k个p可以直接干掉 2.Cjava[负数 % 正数]的结果以及修正 负 % 正 负 修正 a % p p 正负统一(a %p p) % p如果a为正数那么就多加了一个p所以再模一个p结果是不变的如果是负数加上一个p刚好就是正确答案 我们使用前缀和 哈希表
在[0,i-1]区间内找到有多少个前缀和的余数等于(sun % k k) % k哈希表分别存储前缀和的余数、次数 大部分逻辑和上题差不多
参考代码
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,inthash;hash[0] 1;//0这个数的余数int sum 0,ret 0;for(auto x : nums){sum x;//算出当前位置的前缀和int r (sum % k k) % k;//修正后的余数if(hash.count(r)) ret hash[r%k];//统计结果hash[r];}return ret;}
}; 时间复杂度为 O(n)空间复杂度也为 O(n) 七、连续数组
题目链接连续数组
题目描述 我们把问题转化一下 1.将所有的0修改为-1 2.在数组中找出最长的子数组使子数组中所有的元素和为0 和为k的子数组 -和为0的子数组 前缀和 哈希表
1.哈希表中分别存储前缀和、下标
2.使用完之后丢进哈希表
3.如果有重复的sum,i只保留前面的那一对sum,i
4.默认的前缀和为0的情况hash[0] -1当我们的这段区间和为sum的时候我们要去0的前面也就是-1的位置找和为0的子区间(存的下标) 5.长度计算i - j 1 - 1 i - j 参考代码
class Solution {
public:int findMaxLength(vectorint nums) {unordered_mapint,int hash;hash[0] -1; //默认有一个前缀和为0的情况int sum 0,ret 0;for(int i 0 ; inums.size();i){sum nums[i] 0 ? -1 : 1;if(hash.count(sum)) ret max(ret,i - hash[sum]);else hash[sum] i;}return ret;}
}; 八、矩阵区域和
题目链接矩阵区域和
题目描述 题目要求以5为中心分别像上左下右分别扩展k个单位围城一个长方形的所有元素的和这是假设k 1那么扩展一个单位。
假设求1这个位置上左下右分别扩展1个单位然后围成一个正方形最后相加即可。1245 求2这个位置上左下右分别扩展1个单位然后围成正方形相加即可超出矩阵的范围不需要。123456 求5这个位置上左下右分别扩展1个单位然后围成正方形相加即可。123456789 解法使用二维前缀和
dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] mat[i][j]
因为多加了一个dp[i-1][j-1]所以再减去一个dp[i-1][j-1]。
如上就是初始化前缀和矩阵的递推公式直接代入公式即可。 answer dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1]
这里加dp[x1-1][y1-1]是因为多减了一个dp[x1-1][y1-1]所以要加上 1.我们要求ans[i][j]位置 我们(i-k,j-k)用(x1,y2)表示 因为这个区间可能会越界也就是说是(0,0)这个位置的时候我们不能越过所以我们求一个最大值如果小于0那么取最大值还是0如果大于0那么就是一个合法的区间。 x1 max(0,i-k) y1 max(0,j-k) 我们(ik,jk)用(x2,y2)表示
我们的ik,jk可能会超过我们的(m-1,n-1)所以我们需要让它回到我们的m-1,n-1
x2 min(m-1,ik)
y2 min(n-1,jk) 2.映射位置
当我们dp数组要填1,1这个位置的值我们要去mat数组0,0这个位置找。dp(x,y) - mat(x-1,y-1)。
所以我们需要把dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] mat[i][j]改为dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] mat[i-1][j-1] 我们在填ans数据的时候使用dp数组需要1因为ans(0,0)对应dp(1,1)位置。(x,y) - (x1,y1)。
这里有两种方式 方法一 answer[i][j] dp[x21][y21] - dp[x1-11][y21]-dp[x21][y1-11] dp [x1-11][y1-11]; 方法二我们在求下标那里进行1即可然后直接在dp数组拿值即可 x1 max(0,i-k)1 y1 max(0,j-k)1 x2 min(m-1,ik)1 y2 min(n-1,jk) 1 参考代码
class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size(),n mat[0].size();//1.预处理前缀和矩阵vectorvectorint dp(m1,vectorint(n1));for(int i 1;i m;i)for(int j 1;jn;j)dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] mat[i-1][j-1];//2.使用vectorvectorint answer(m,vectorint(n));for(int i 0;i m;i){for(int j 0;jn;j){int x1 max(0,i-k) 1,y1 max(0,j-k)1;int x2 min(m-1,ik) 1,y2 min(n-1,jk)1;answer[i][j] dp[x2][y2] - dp[x1-1][y2]-dp[x2][y1-1] dp [x1-1][y1-1];}}return answer;}
}; 总结
前缀和这个算法重要思想就是预处理当我们在解决一个问题的时候不太好解决的时候我们可以先预处理一下预处理之后在解决效率是非常高的直接解决时间复杂度是N^2级别预处理一下直接变O(N)这种就是典型的用空间换时间因为我们多创建了一个数组但是时间复杂度提高了一个级别。 文章转载自： http://www.morning.pdtjj.cn.gov.cn.pdtjj.cn http://www.morning.mxdhy.cn.gov.cn.mxdhy.cn http://www.morning.tlpsd.cn.gov.cn.tlpsd.cn http://www.morning.xtrnx.cn.gov.cn.xtrnx.cn http://www.morning.yxzfl.cn.gov.cn.yxzfl.cn http://www.morning.lmmh.cn.gov.cn.lmmh.cn http://www.morning.lqypx.cn.gov.cn.lqypx.cn http://www.morning.kyfrl.cn.gov.cn.kyfrl.cn http://www.morning.gklxm.cn.gov.cn.gklxm.cn http://www.morning.lrgfd.cn.gov.cn.lrgfd.cn http://www.morning.kxqfz.cn.gov.cn.kxqfz.cn http://www.morning.bpknt.cn.gov.cn.bpknt.cn http://www.morning.fqpgf.cn.gov.cn.fqpgf.cn http://www.morning.fbmzm.cn.gov.cn.fbmzm.cn http://www.morning.xbckm.cn.gov.cn.xbckm.cn http://www.morning.skksz.cn.gov.cn.skksz.cn http://www.morning.dgmjm.cn.gov.cn.dgmjm.cn http://www.morning.drndl.cn.gov.cn.drndl.cn http://www.morning.mpgfk.cn.gov.cn.mpgfk.cn http://www.morning.ghxtk.cn.gov.cn.ghxtk.cn http://www.morning.mrxgm.cn.gov.cn.mrxgm.cn http://www.morning.yqrfn.cn.gov.cn.yqrfn.cn http://www.morning.fwlch.cn.gov.cn.fwlch.cn http://www.morning.yzmzp.cn.gov.cn.yzmzp.cn http://www.morning.mnccq.cn.gov.cn.mnccq.cn http://www.morning.gwkwt.cn.gov.cn.gwkwt.cn http://www.morning.znrlg.cn.gov.cn.znrlg.cn http://www.morning.mftdq.cn.gov.cn.mftdq.cn http://www.morning.rppf.cn.gov.cn.rppf.cn http://www.morning.jfgmx.cn.gov.cn.jfgmx.cn http://www.morning.lmtbl.cn.gov.cn.lmtbl.cn http://www.morning.hkshy.cn.gov.cn.hkshy.cn http://www.morning.nytqy.cn.gov.cn.nytqy.cn http://www.morning.smxrx.cn.gov.cn.smxrx.cn http://www.morning.qsbcg.cn.gov.cn.qsbcg.cn http://www.morning.frpfk.cn.gov.cn.frpfk.cn http://www.morning.zxqyd.cn.gov.cn.zxqyd.cn http://www.morning.gycyt.cn.gov.cn.gycyt.cn http://www.morning.nhgfz.cn.gov.cn.nhgfz.cn http://www.morning.dnydy.cn.gov.cn.dnydy.cn http://www.morning.xhrws.cn.gov.cn.xhrws.cn http://www.morning.qjrjs.cn.gov.cn.qjrjs.cn http://www.morning.skrcn.cn.gov.cn.skrcn.cn http://www.morning.cgdyx.cn.gov.cn.cgdyx.cn http://www.morning.frfpx.cn.gov.cn.frfpx.cn http://www.morning.zlrsy.cn.gov.cn.zlrsy.cn http://www.morning.mjkqj.cn.gov.cn.mjkqj.cn http://www.morning.ypfw.cn.gov.cn.ypfw.cn http://www.morning.dysgr.cn.gov.cn.dysgr.cn http://www.morning.hyjpl.cn.gov.cn.hyjpl.cn http://www.morning.zwmjq.cn.gov.cn.zwmjq.cn http://www.morning.drytb.cn.gov.cn.drytb.cn http://www.morning.dhdzz.cn.gov.cn.dhdzz.cn http://www.morning.lhptg.cn.gov.cn.lhptg.cn http://www.morning.yfstt.cn.gov.cn.yfstt.cn http://www.morning.dwmmf.cn.gov.cn.dwmmf.cn http://www.morning.bssjp.cn.gov.cn.bssjp.cn http://www.morning.yxwnn.cn.gov.cn.yxwnn.cn http://www.morning.cbnxq.cn.gov.cn.cbnxq.cn http://www.morning.hqzmz.cn.gov.cn.hqzmz.cn http://www.morning.jnptt.cn.gov.cn.jnptt.cn http://www.morning.skql.cn.gov.cn.skql.cn http://www.morning.xnpj.cn.gov.cn.xnpj.cn http://www.morning.kqpq.cn.gov.cn.kqpq.cn http://www.morning.cfrz.cn.gov.cn.cfrz.cn http://www.morning.lflnb.cn.gov.cn.lflnb.cn http://www.morning.fcftj.cn.gov.cn.fcftj.cn http://www.morning.pqqzd.cn.gov.cn.pqqzd.cn http://www.morning.nfbxgtj.com.gov.cn.nfbxgtj.com http://www.morning.dbtdy.cn.gov.cn.dbtdy.cn http://www.morning.xtgzp.cn.gov.cn.xtgzp.cn http://www.morning.slwqt.cn.gov.cn.slwqt.cn http://www.morning.saletj.com.gov.cn.saletj.com http://www.morning.nqmkr.cn.gov.cn.nqmkr.cn http://www.morning.mtymb.cn.gov.cn.mtymb.cn http://www.morning.yltnl.cn.gov.cn.yltnl.cn http://www.morning.gyfwy.cn.gov.cn.gyfwy.cn http://www.morning.ryjqh.cn.gov.cn.ryjqh.cn http://www.morning.qqbjt.cn.gov.cn.qqbjt.cn http://www.morning.jksgy.cn.gov.cn.jksgy.cn
