html5手机网站开发视频,wordpress 明月浩空,贵阳利于优化的网站,网站百度快照目录 1. 一维前缀和2. 二维前缀和3. 寻找数组中心下标4. 除自身以外数组的乘积5. !和为k的子数字6. !和可被k整除的子数组7. !连续数组8. 矩阵区域和 1. 一维前缀和 题目信息#xff1a; 题目链接#xff1a; 一维前缀和思路#xff1a;求前缀和数组#xff0c;sum dp[r] … 目录 1. 一维前缀和2. 二维前缀和3. 寻找数组中心下标4. 除自身以外数组的乘积5. !和为k的子数字6. !和可被k整除的子数组7. !连续数组8. 矩阵区域和 1. 一维前缀和 题目信息 题目链接 一维前缀和思路求前缀和数组sum dp[r] - dp[l - 1] #include iostream
#include vector
using namespace std;int main()
{int n 0;int q 0;cin n q;//先求前缀和数组int num 0;//计算时可能溢出vectorlong long dp;dp.push_back(0);for(int i 0; i n; i){cin num;dp.push_back(num dp[i]);}//求询问区间之和//dp[i] - dp[i - 1]//计算时可能溢出vectorlong long ret;int left 0,right 0;for(int i 0; i q; i){cin left right;ret.push_back(dp[right] - dp[left - 1]);}for(auto e : ret){cout e endl;}return 0;
}优化 int main()
{int n 0;int q 0;cin n q;//先求前缀和数组int num 0;//默认初始化为0vectorint arr(n 1);for(int i 1; i n 1; i){cin num;arr[i] num;}//防溢出vectorlong long dp(n 1);for(int i 1; i n 1; 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. 二维前缀和 题目信息 题目链接 二维前缀和思路二维前缀和 int main()
{int n 0, m 0, q 0;//先遍历得值 cin n m q;vectorvectorlong long arr;vectorlong long part(m 1);for (int i 0; i n 1; i){arr.push_back(part);}vectorvectorlong long dp(arr);for (int i 1; i n; i){for (int j 1; j m; j){cin arr[i][j];}}//求前缀和数组for (int i 1; i n; i){for (int j 1; j m; j){dp[i][j] arr[i][j] dp[i - 1][j] dp[i][j - 1] - dp[i - 1][j - 1];}}//求区间值//x1,y1小x2,y2大int x1, x2, y1, y2 0;while (q--){cin x1 y1 x2 y2;cout dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] dp[x1 - 1][y1 - 1] endl;}return 0;
}3. 寻找数组中心下标 题目信息 题目链接 寻找数组的中心下标思路正向与逆向前缀和数组边界处理特殊情况处理 class Solution
{
public:int pivotIndex(vectorint nums){int n nums.size();vectorint dp1(n);vectorint dp2(n);//空if(nums.size() 1){return 0;}int left 0, right nums.size() - 1;//求前缀和数组//顺序while (left nums.size()){if (left 0){dp1[left] nums[left] dp1[left - 1];}else{dp1[left] nums[left];}left;}//倒序while (right 0){if (right nums.size() - 1){dp2[right] nums[right] dp2[right 1];}else{dp2[right] nums[right];}right--;}//遍历求中间结点for (int cur 0; cur nums.size(); cur){//dp1顺序//dp2倒序if (cur 0){if (dp2[cur 1] 0){return cur;}}else if (cur nums.size() - 1){if (dp1[cur - 1] 0){return cur;}}else{if (dp1[cur - 1] dp2[cur 1]){return cur;}}}return -1;}
};优化
class Solution
{
public:int pivotIndex(vectorint nums) {int n nums.size();//顺序vectorint f(n);//逆序vectorint g(n);//边界问题特殊处理f[0] 0;//f[i] - [0, i - 1]for(int i 1; i n; i){f[i] nums[i - 1] f[i - 1];}g[n - 1] 0;for(int i n - 2; i 0; i--){g[i] g[i 1] nums[i 1];}for(int i 0; i n; i){if(f[i] g[i]){return i;}}return -1;}
};4. 除自身以外数组的乘积 题目信息 题目链接 除自身以外数组的乘积思路前缀 后缀数组 class Solution
{
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint f(n);vectorint g(n);f[0] nums[0];for(int i 1; i n; i){f[i] nums[i] * f[i - 1];}g[n - 1] nums[n - 1];for(int i n - 2; i 0; i--){g[i] nums[i] * g[i 1];}vectorint ret(n);for(int i 0; i n; i){if(i 0){ret[i] g[i 1];}else if(i n - 1){ret[i] f[i - 1];}else{ret[i] g[i 1] * f[i - 1];}}return ret;}
};优化
class Solution
{
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint f(n);vectorint g(n);f[0] 1;//顺序for(int i 1; i n; i){f[i] f[i - 1] * nums[i - 1];}g[n - 1] 1;//逆序for(int i n - 2; i 0; i--){g[i] g[i 1] * nums[i 1];}vectorint ret(n);for(int i 0; i n; i){ret[i] f[i] * g[i];}return ret;}
};5. !和为k的子数字 题目信息 题目链接 和为k的子数组思路前缀和元素没有单调性无法使用滑动窗口逆向求sum - k可以求得为i为尾的所有数组 class Solution
{
public:int subarraySum(vectorint nums, int k) {int ret 0;unordered_mapint ,int hash;//sum - k 0时即sum就为khash[0] 1;int sum 0;//用哈希表代替遍历for(auto e : nums){sum e;if(hash.count(sum - k)){ret hash[sum - k];}//插入哈希表//可能存在重复前缀和hash[sum];}return ret;}
};6. !和可被k整除的子数组 题目信息 题目链接 和可被k整除的子数组思路前缀和哈希表同余定理C中负数除以整数的余数修正(num % k k) % k class Solution
{
public:int subarraysDivByK(vectorint nums, int k) {int sum 0;unordered_mapint,int hash;int ret 0;int count 0;//sum % k 本身就符合要求hash[0] 1;for(auto e : nums){sum e;//(sum1 - sum2) % k 0//同余定理//负数除整数的余数//哈希表中存余数if(hash.count((sum % k k) % k)){ret hash[(sum % k k) % k];}hash[(sum % k k) % k];}return ret;}
};7. !连续数组 题目信息 题目链接 连续数组 3.思路前缀加哈希表求长度记录下标 class Solution
{
public:int findMaxLength(vectorint nums) {for(auto e : nums){if(e 0){e -1;}}unordered_mapint,int hash;int sum 0;int len 0;//细节刚好sum为0hash[0] -1;for(int i 0; i nums.size(); i){//将所有的前缀和与对应下标记录至哈希表中sum nums[i];//返回的是长度最长数组的长度if(hash.count(sum) len i - hash[sum]){len i - hash[sum];}//不存在添加下标if(!hash.count(sum)){hash[sum] i;}}return len;}
};8. 矩阵区域和 题目信息 题目链接 矩阵区域和思路前缀和二维数组边界问题分析 思路 边界问题
class Solution
{
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k){vectorint part1(mat[0].size(), 0);vectorvectorint answer(mat.size(), part1);vectorint part2(mat[0].size() 1, 0);vectorvectorint dp(mat.size() 1, part2);//二维数组的前缀和for (int i 1; i dp.size(); i){for (int j 1; j dp[0].size(); j){dp[i][j] dp[i - 1][j] dp[i][j - 1] - dp[i - 1][j - 1] mat[i - 1][j - 1];}}for (int i 0; i mat.size(); i){for (int j 0; j mat[0].size(); j){int sum 0;//右下角//边界情况修正int pos1 i k 1;int pos2 j k 1;if (pos1 dp.size()){pos1 dp.size() - 1;}if (pos2 dp[0].size()){pos2 dp[0].size() - 1;}sum dp[pos1][pos2];//右上角pos1 i - k;pos2 j k 1;//i符合j不符合if (pos1 1 pos2 dp[0].size()){pos2 dp[0].size() - 1;}if (pos1 1 pos2 dp[0].size()){sum - dp[pos1][pos2];}//左下角pos1 i k 1;pos2 j - k;//i不符合j符合if (pos1 dp.size() pos2 1){pos1 dp.size() - 1;}if (pos1 dp.size() pos2 1){sum - dp[pos1][pos2];}//左上角if (i - k 1 j - k 1){sum dp[i - k][j - k];}answer[i][j] sum;}}return answer;}
};
