目录
一：一维前缀和
二：二维前缀和
三:LeetCode OJ练习
1.第一题
2.第二题
3.第三题
4.第四题
5.第五题
6.第六题
一：一维前缀和
这里通过例题来引出
牛客_DP34 【模板】前缀和
画图分析:
具体代码:
#include <iostream>
#include <vector>
using namespace std;int main()
{//1.读入数据int l=0,r=0,n=0,q=0;cin>>n>>q;vector<int> arr(n+1);for(int i=1;i<=n;++i) cin>>arr[i];//2.预处理出来一个前缀和数组vector<long long> dp(n+1);//防止溢出for(int i=1;i<=n;++i){dp[i]=dp[i-1]+arr[i];//dp[0]=0,不影响计算结果}//3.使用前缀和数组while(q--){cin>>l>>r;cout<<dp[r]-dp[l-1]<<endl;}return 0;
}二：二维前缀和
这里通过例题来引出
牛客_DP35 【模板】二维前缀和
画图分析:
具体代码:
#include <iostream>
#include <vector>
using namespace std;int main()
{//读入数据int n=0,m=0,q=0;cin>>n>>m>>q;vector<vector<int>>arr (n+1,vector<int>(m+1));for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)cin>>arr[i][j];//预处理前缀和矩阵vector<vector<long long>> dp(n+1,vector<long long>(m+1));//防止数据溢出for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)dp[i][j]=dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1];//使用前缀和矩阵int x1=0,y1=0,x2=0,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;
}三:LeetCode OJ练习
1.第一题
LeetCode_724 寻找数组的中心下标
画图分析:
具体代码:
int pivotIndex(vector<int>& nums) {int n=nums.size();//预处理前缀和数组+后缀和数组vector<int> f(n),g(n);for(int i=1;i<n;++i)f[i]=f[i-1]+nums[i-1];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;}2.第二题
LeetCode_238 除自身以外数组的乘积
画图分析:
具体代码:
vector<int> productExceptSelf(vector<int>& nums) {int n=nums.size();//1.预处理前缀积数组和后缀积数组vector<int> f(n),g(n);f[0]=g[n-1]=1;//处理细节问题for(int i=1;i<n;++i)f[i]=f[i-1]*nums[i-1];for(int i=n-2;i>=0;--i)g[i]=g[i+1]*nums[i+1];//2.使用vector<int> ret(n);for(int i=0;i<n;++i)ret[i]=f[i]*g[i];return ret;}3.第三题
LeetCode_560 和为k的子数组
画图分析:
具体代码:
int subarraySum(vector<int>& nums, int k) {unordered_map<int,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;}4.第四题
LeetCode_974 和可被k整除的子数组
画图分析:
具体代码:
int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;//统计前缀和的余数及对应个数hash[0%k]=1;int sum=0,ret=0;for(auto e:nums){sum+=e;//算出当前位置的前缀和int r=(sum%k+k)%k;//修正后的余数if(hash.count(r)) ret+=hash[r];//统计结果hash[r]++;}return ret;}5.第五题
LeetCode_525 连续数组
画图分析:
具体代码:
int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;hash[0]=-1;//默认有一个前缀和为0的情况int sum=0,ret=0;for(int i=0;i<nums.size();++i){sum+=nums[i]==0? -1:1;//计算当前位置的前缀和if(hash.count(sum)) ret=max(ret,i-hash[sum]);else hash[sum]=i;}return ret;}6.第六题
OJ传送门 LeetCode_1314 矩阵区域和
画图分析:
具体代码:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m=mat.size(),n=mat[0].size();//1.预处理一个前缀和矩阵vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1];//2.使用vector<vector<int>> ret(m,vector<int>(n));for(int i=0;i<m;++i)for(int j=0;j<n;++j){int x1=max(0,i-k)+1,y1=max(0,j-k)+1;int x2=min(m-1,i+k)+1,y2=min(n-1,j+k)+1;ret[i][j]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];}return ret;}
