做微商能利用的网站有哪些,海口旅游类网站建设,做汽车团购的网站,wordpress仿hexo主题一、【模版】前缀和
1.链接
【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)
2.描述 3.思路
前缀和的思想其实就是一种简单的动态规划#xff0c;以i位置记录从头位置到i位置的和#xff0c;然后间接的求一段连续区间的数组和#xff0c;时间复杂度是O#xff08;n以i位置记录从头位置到i位置的和然后间接的求一段连续区间的数组和时间复杂度是On Oq这种思想在实际中是为了应对多次查询的情况当q特别大时采用这种方式的时间复杂度就会较低 4.参考代码
#include iostream
#include vector
using namespace std;int main()
{int n,q;cin n q;vectorint arr(n1,0);for(int i 1;i n;i) cin arr[i];vectorlong long dp(n1,0);for(int i 1;i n ; i) dp[i] dp[i-1] arr[i];while(q--){int l,r;cin l r;cout dp[r] - dp[l-1] endl;}return 0;
} 二、二维前缀和
1.链接
【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)
2.描述 3.思路
该题我们采用动态规划的定式思路去分析得到前缀和的表并且分析如何使用 4.参考代码
核心的思路就是上面的动归分析已经如何使用前缀和表格的部分剩下的就是在实际写代码时候的一些细节
1.测试用例中包含较大的数据因此在dp表格中存放的值类型需要使用long long
2.一般按照思路是先载入数据然后再动归建立dp表但由于我们这里dp表和arr都选择使用多一行一列的辅助位置去进行的初始化这两个步骤可以放在同一个for循环里一起执行但先后顺序不能变一定是先载入arr的数据再去执行dp
#include iostream
using namespace std;
#includevectorint main()
{//加载数据int n,m,q;cin n m q;vectorvectorint arr(n1,vectorint(m1,0));vectorvectorlong long dp(n1,vectorlong long(m1,0));//利用动态规划思路建立前缀和的表格//写代码的时候发现两个步骤可以合并因此放在一起执行for(int i 1;in;i){for(int j 1;jm;j){cin arr[i][j];//加载数据dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] arr[i][j];//动归创建前缀和表格}}int x1,x2,y1,y2;//开始查询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;
} 三、寻找数组的中心下标
1.链接
724. 寻找数组的中心下标 - 力扣LeetCode
2.描述 3.思路
先建立前缀和表格然后遍历一遍下标位置去比对当前下标的前后两个部分的和是否相同若是相同则说明当前下标就是目标值直接返回若是遍历结束后都没有找到说明不存在返回-1
要注意前缀表中和题目给的数组两者之间的映射关系最好画图去分析又或者可以建立多一个后缀表去对应遍历 4.参考代码
class Solution {
public:int pivotIndex(vectorint nums) {int n nums.size();vectorint dp(n1,0);for(int i 1;in;i) dp[i] dp[i-1] nums[i-1];for(int i 0;in;i){if(dp[i] dp[n] - dp[i1]) return i;}return -1;}
}; 四、除自身以外数组的乘积
1.链接
238. 除自身以外数组的乘积 - 力扣LeetCode
2.描述 3.思路
题目要求的数组是除开自己的其余所有数的乘积那么可以将ret[i]分成两部分
1.nums[0] * nums[1] * nums[2] * ... * nums[i-1] i位置的左半部分乘积
2.nums[i1] * nums[i2] * nums[i3] * ... * nums[n-1]i位置的右半部分乘积
因此我们可以利用前缀和的思想去将前半部分和后半部分分别进行制表
head[i]:表示以i位置结束从第头到该位置的乘积
tail[i]:表示从i位置开始到最末尾的乘积
然后遍历填表即可
4.参考代码
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint ret(n);vectorint head(n1,1);//添加辅助位要注意映射关系vectorint tail(n2,1);//注意这里需要先初始化tail的第一个值for(int i 1;in;i) head[i] head[i-1]*nums[i-1];for(int i n;i1;i--) tail[i] tail[i1]*nums[i-1];//得到两个表格后遍历填表即可for(int i 0;in;i) ret[i] head[i]*tail[i2];return ret;}
}; 五、和为k的子数组
1.链接
560. 和为 K 的子数组 - 力扣LeetCode
2.描述 3.思路 4.参考代码
class Solution {
public:int subarraySum(vectorint nums, int k) {int sum 0;mapint,int hash;int count 0;for(int i 0;inums.size();i){hash[sum];sum nums[i];//此时sum为i位置的前缀和count hash[sum-k];}return count;}
};
5.代码分析 六、和可被K整除的子数组
1.链接
974. 和可被 K 整除的子数组 - 力扣LeetCode
2.描述 3.思路 4.参考代码
class Solution
{
public:int subarraysDivByK(vectorint nums, int k) {mapint,int hash;int sum nums[0];int count 0;for(int i 0;inums.size();i){hash[(sum%kk)%k];sumnums[i];count hash[(sum%kk)%k];}return count;}
}; 七、连续数组
1.链接
525. 连续数组 - 力扣LeetCode
2.描述 3.思路
改题目若是将所有的0都换成-1则依然和上一题的思路是一样的都是通过前缀和去转化 4.参考代码
class Solution
{
public:int findMaxLength(vectorint nums) {unordered_mapint,int hash;int ret 0;int sum 0;hash[0] -1;for(int i 0;inums.size();i){sumnums[i] 0? -1 : 1;//将数据转化一下if(hash.count(sum)) ret max(ret,i-hash[sum]);else hash[sum] i;}return ret;}
}; 八、矩阵区域和
1.链接
1314. 矩阵区域和 - 力扣LeetCode
2.描述 这题描述较复杂大致意思就是给你一个m*n的矩阵并且给你一整数k然后你得返回一个相同规模的矩阵而这个矩阵内的数据要求是
以【ij】位置向上下左右各延伸k个单位然后围成的矩阵和越界的部分视为0例如 3.思路
这题就是对二维前缀和的一个应用对二维前缀和的表格建立和使用需要熟练掌握分析而不要去死记公式得到二维前缀和表和得到使用方法后再根据这题进行分析这里不重复分析随便花个草图去分析即可 建表的递推公式dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] mat[i][j]
使用表格的公式dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1]
分析
这题首先是如何确定x1、y1、x2、y2的问题画图分析可得太简单了略
(x1,y1) i-k,y-k (x2,y2) ik,yk
除了找到对应的矩阵区间我们很容易想到还需要对边界条件进行除了i-k和j-k是有可能越界的因此最多我们不能让它们小于0,0的位置ik和jk同理最大不能大于m-1n-1的位置
x1 max(0,i-k); y1 max(0,y-k); x2 min(m-1,ik); y2 min(n-1,jk);
还有一个细节就是下标的映射关系要注意因为在初始化dp表前缀和表时我们会添加一个辅助位而题目给的数组是从0开始的dp表则是从1开始所以写代码时要注意映射关系即可 4.参考代码
class Solution
{
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size();int n mat[0].size();vectorvectorint dp(m1,vectorint(n1,0));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 answer(m,vectorint(n));for(int i 0;im;i){for(int j 0;jn;j){int x1 max(0,i-k), y1max(0,j-k);int x2 min(m-1,ik), y2 min(n-1,jk);answer[i][j] dp[x21][y21] - dp[x1][y21] - dp[x21][y1] dp[x1][y1];//注意映射关系}}return answer;}
}; 总结
本篇内容是关于前缀和的算法思想和应用整理了一些经典的题目从简单到难逐步递进提供链接可以直接到力扣上做也提供了描述可以直接通过看本篇文章去尝试思考解题提供了参考思路和测试通过的代码C整理学习下来后个人认为一个是需要掌握一维和二维的表格建立和基本使用还有相对较难的但也有迹可循的一种用前缀和将题目转化利用哈希表去优化效率的思想参考五到七题这个思路相对重要
