广州建网站的公司 白云区,北京搜狗建网站的电话,网站页面设计培训,数字货币网站开发优选算法第四讲#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;}
};
