算法修炼之路之前缀和
目录
一：一维前缀和
这里通过例题来引出
画图分析:
具体代码:
#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;
}二：二维前缀和
这里通过例题来引出
画图分析:
具体代码:
#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.第一题
画图分析:
具体代码:
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.第二题
画图分析:
具体代码:
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.第三题
画图分析:
具体代码:
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.第四题
画图分析:
具体代码:
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.第五题
画图分析:
具体代码:
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.第六题
画图分析:
具体代码:
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;
}原文地址：https://blog.csdn.net/Miwll/article/details/142733928
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！