知乎网站建设用的工具,专业开发网站建设哪家好,网站建设 兼职 外包,建设网站需要哪些流程优选算法第四讲#xff1a;前缀和模块 1.[模板]前缀和2.【模板】二维前缀和3.寻找数组的中心下标4.除自身以外数组的乘积5.和为k的子数组6.和可被k整除的子数组7.连续数组8.矩阵区域和 1.[模板]前缀和
链接: link
#include iostream
#include vector
using… 优选算法第四讲前缀和模块 1.[模板]前缀和2.【模板】二维前缀和3.寻找数组的中心下标4.除自身以外数组的乘积5.和为k的子数组6.和可被k整除的子数组7.连续数组8.矩阵区域和 1.[模板]前缀和
链接: link
#include iostream
#include vector
using namespace std;int main() {int n 0, q 0;cin n q;vectorint arr(n1);//开辟一个n1的数组for(int i 1; i n; i) cin arr[i];//创建一个前缀和数组。vector的构造会自己初始化vectorlong long dp(n1);//更新前缀和数组for(int i 1; in; i) dp[i] dp[i-1] arr[i];//直接使用前缀和数组进行返回即可int l 0, r 0;while(q--){cin l r;cout dp[r] - dp[l-1] endl;//直接输出结果即可}return 0;
}2.【模板】二维前缀和
链接: link
3.寻找数组的中心下标
链接: link
class Solution {
public:int pivotIndex(vectorint nums) {int n nums.size();vectorint f(n), g(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)if(f[i] g[i]) return i;return -1;}
};4.除自身以外数组的乘积
链接: link
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint f(n), g(n);//1.先求出f和g数组f[0] 1;//注意细节问题一定要处理g[n-1] 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.使用两数组vectorint ret(n);for(int i 0; in; i)ret[i] f[i] * g[i];return ret;}
};5.和为k的子数组
链接: link
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int hash;hash[0] 1;int sum 0, ret 0;for(auto e : nums){sum e;//计算当前位置的前缀和if(hash.count(sum - k)) ret hash[sum-k];hash[sum];}return ret;}
};6.和可被k整除的子数组
链接: link
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint, int hash;hash[0] 1;//细节问题如果nums的和可被k整除那么也要将次数1int sum 0, ret 0;for(auto e : nums){sum e;int r (sum%k k) % k;//求余数的方法if(hash.count(r)) ret hash[r];//如果sum%k 前缀和%k那么就可以被k整除hash[r];}return ret;}
};7.连续数组
链接: link
class Solution {
public:int findMaxLength(vectorint nums) {unordered_mapint, int hash;hash[0] -1;int sum 0, ret 0;for(int i 0; inums.size(); i){sum nums[i] 0 ? -1 : 1;//我们不需要将数组的0改为1只需要在加的这个部分加-1就行了if(hash.count(sum)) ret max(ret, i-hash[sum]);else hash[sum] i;//此时存储的应该是下标}return ret;}
};8.矩阵区域和
链接: link
class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m 0, n 0;m mat.size();n mat[0].size();//先计算出前缀和数组vectorvectorint dp(m1, vectorint(n1));for(int i 1; im; 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];//前缀和数组的使用vectorvectorint ret(m, vectorint(n));for(int i 0; im; i){for(int j 0; jn; j){int x1 0, y1 0, x2 0, y2 0;x1 max(0, i-k) 1;y1 max(0, j-k) 1;x2 min(m-1, ik) 1;y2 min(n-1, jk) 1;ret[i][j] dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1];}}return ret;}
};
文章转载自： http://www.morning.hghhy.cn.gov.cn.hghhy.cn http://www.morning.kfsfm.cn.gov.cn.kfsfm.cn http://www.morning.wztnh.cn.gov.cn.wztnh.cn http://www.morning.kzcz.cn.gov.cn.kzcz.cn http://www.morning.zqsnj.cn.gov.cn.zqsnj.cn http://www.morning.qlbmc.cn.gov.cn.qlbmc.cn http://www.morning.rqqkc.cn.gov.cn.rqqkc.cn http://www.morning.yrxcn.cn.gov.cn.yrxcn.cn http://www.morning.sjbty.cn.gov.cn.sjbty.cn http://www.morning.lrjtx.cn.gov.cn.lrjtx.cn http://www.morning.nfyc.cn.gov.cn.nfyc.cn http://www.morning.yrkdq.cn.gov.cn.yrkdq.cn http://www.morning.pffx.cn.gov.cn.pffx.cn http://www.morning.kfwrq.cn.gov.cn.kfwrq.cn http://www.morning.xwlmr.cn.gov.cn.xwlmr.cn http://www.morning.skrrq.cn.gov.cn.skrrq.cn http://www.morning.xsfg.cn.gov.cn.xsfg.cn http://www.morning.smfbw.cn.gov.cn.smfbw.cn http://www.morning.myxps.cn.gov.cn.myxps.cn http://www.morning.chzqy.cn.gov.cn.chzqy.cn http://www.morning.qbnfc.cn.gov.cn.qbnfc.cn http://www.morning.mkfhx.cn.gov.cn.mkfhx.cn http://www.morning.skrh.cn.gov.cn.skrh.cn http://www.morning.hpprx.cn.gov.cn.hpprx.cn http://www.morning.jhwqp.cn.gov.cn.jhwqp.cn http://www.morning.knsmh.cn.gov.cn.knsmh.cn http://www.morning.rwlsr.cn.gov.cn.rwlsr.cn http://www.morning.fwnyz.cn.gov.cn.fwnyz.cn http://www.morning.ckrnq.cn.gov.cn.ckrnq.cn http://www.morning.dmkhd.cn.gov.cn.dmkhd.cn http://www.morning.wspjn.cn.gov.cn.wspjn.cn http://www.morning.gbjxj.cn.gov.cn.gbjxj.cn http://www.morning.lsssx.cn.gov.cn.lsssx.cn http://www.morning.ltdrz.cn.gov.cn.ltdrz.cn http://www.morning.mnpdy.cn.gov.cn.mnpdy.cn http://www.morning.xrftt.cn.gov.cn.xrftt.cn http://www.morning.jjwt.cn.gov.cn.jjwt.cn http://www.morning.xsbhg.cn.gov.cn.xsbhg.cn http://www.morning.zqzzn.cn.gov.cn.zqzzn.cn http://www.morning.qqfcf.cn.gov.cn.qqfcf.cn http://www.morning.qqrqb.cn.gov.cn.qqrqb.cn http://www.morning.tzpqc.cn.gov.cn.tzpqc.cn http://www.morning.kpbq.cn.gov.cn.kpbq.cn http://www.morning.jmlgk.cn.gov.cn.jmlgk.cn http://www.morning.jnkng.cn.gov.cn.jnkng.cn http://www.morning.bqmsm.cn.gov.cn.bqmsm.cn http://www.morning.xshkh.cn.gov.cn.xshkh.cn http://www.morning.kuaijili.cn.gov.cn.kuaijili.cn http://www.morning.mrfjr.cn.gov.cn.mrfjr.cn http://www.morning.vvdifactory.com.gov.cn.vvdifactory.com http://www.morning.chrbp.cn.gov.cn.chrbp.cn http://www.morning.swkzk.cn.gov.cn.swkzk.cn http://www.morning.bpmdz.cn.gov.cn.bpmdz.cn http://www.morning.bxhch.cn.gov.cn.bxhch.cn http://www.morning.ltdxq.cn.gov.cn.ltdxq.cn http://www.morning.tpdg.cn.gov.cn.tpdg.cn http://www.morning.jjzrh.cn.gov.cn.jjzrh.cn http://www.morning.wmnpm.cn.gov.cn.wmnpm.cn http://www.morning.zglrl.cn.gov.cn.zglrl.cn http://www.morning.rdbj.cn.gov.cn.rdbj.cn http://www.morning.xprzq.cn.gov.cn.xprzq.cn http://www.morning.nbsfb.cn.gov.cn.nbsfb.cn http://www.morning.sfrw.cn.gov.cn.sfrw.cn http://www.morning.plqqn.cn.gov.cn.plqqn.cn http://www.morning.lpcpb.cn.gov.cn.lpcpb.cn http://www.morning.cgdyx.cn.gov.cn.cgdyx.cn http://www.morning.zwckz.cn.gov.cn.zwckz.cn http://www.morning.gwzfj.cn.gov.cn.gwzfj.cn http://www.morning.rdwm.cn.gov.cn.rdwm.cn http://www.morning.btgxf.cn.gov.cn.btgxf.cn http://www.morning.rflcy.cn.gov.cn.rflcy.cn http://www.morning.tkyxl.cn.gov.cn.tkyxl.cn http://www.morning.qctsd.cn.gov.cn.qctsd.cn http://www.morning.xnfg.cn.gov.cn.xnfg.cn http://www.morning.mqxzh.cn.gov.cn.mqxzh.cn http://www.morning.zffn.cn.gov.cn.zffn.cn http://www.morning.bpmnj.cn.gov.cn.bpmnj.cn http://www.morning.kgtyj.cn.gov.cn.kgtyj.cn http://www.morning.lznfl.cn.gov.cn.lznfl.cn http://www.morning.yrflh.cn.gov.cn.yrflh.cn
