网站建设落后发言,WordPress记录访问者ip,西安巨久科技网站建设,网页界面设计罗军目录 1. 前缀和2. 二维前缀和3. 寻找数组的中心下标4. 除自身以外数组的乘积5. 和为k的子数组6. 和可被K整除的子数组7. 连续数组8. 矩阵区域和 博客主页:酷酷学!!! 感谢关注~ 1. 前缀和 算法思路:
根据题意, 创建一个前缀和数组, dp[i] dp[i -1] arr[i], 再使用前缀和数组,… 目录 1. 前缀和2. 二维前缀和3. 寻找数组的中心下标4. 除自身以外数组的乘积5. 和为k的子数组6. 和可被K整除的子数组7. 连续数组8. 矩阵区域和 博客主页:酷酷学!!! 感谢关注~ 1. 前缀和 算法思路:
根据题意, 创建一个前缀和数组, dp[i] dp[i -1] arr[i], 再使用前缀和数组, 要求的区域ret dp[r] - dp[l-1], 这里我们为什么要这样求dp[i]呢? 还要绕一大圈子, 直接相加不就行了 , 但是如果直接相加求还不如我们的暴力解法呢, 这里还要开辟空间, 但是我们使用dp[i]求解只需遍历一遍数组即可求出前缀和
需要注意:
创建前缀和数组默认从0开始, 如果我们从1开始访问则需要先将数组初始化好,因为dp[i] 的大小可能超过int所以需要创建long long类型的数组.
编写代码:
#include iostream
#include vector
using namespace std;int main()
{int n 0, q 0;cinnq;vectorlong long dp(n1,0);int num 0;for(int i 1; i n; i){cinnum;dp[i] dp[i-1] num;}while(q--){int l,r;cinlr;coutdp[r] - dp[l-1]endl;}return 0;
}
// 64 位输出请用 printf(%lld)2. 二维前缀和 算法思路: 分析题意, 很显然如果我们使用暴力解法一定会超时的. 首先分析题目, 我们可以先预处理出来一个前缀和矩阵如下图所示, 求出每一个dp[i][j] 然后我们使用dp[i][j],根据所求的区域我们就可以找出一个求出结果的公式, 于是我们就可以搞出来一个时间复杂度为O(N)的算法,当然空间复杂度也为O(N). 编写代码:
#includeiostream
#includevector
using namespace std;
int main()
{ int n,m,q;cinnmq;vectorvectorint arr(n1,vectorint(m1));for(int i 1; i n; i){for(int j 1; j m; j){cinarr[i][j];}}vectorvectorlong long dp(n1,vectorlong long(m1));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] - dp[i-1][j-1] arr[i][j];}}int x1,y1,x2,y2;while(q--){cinx1y1x2y2;coutdp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1]endl;}return 0;
}3. 寻找数组的中心下标 算法思路1:
分析题意, 发现可以使用前缀和来解决, 首先预处理出来一个前缀和数组, 然后我们只需在遍历一遍前缀和数组, 只要找到一个位置前面的区域和后面的区域相同, 则就找到了该位置, 但是注意我们的dp是从1开始的所以返回结果需要-1, 如果没有找到返回-1即可, 注意预处理前缀和数组的时候与原数组的映射关系.
编写代码:
class Solution {
public:int pivotIndex(vectorint nums) {int n nums.size();vectorint dp(n1,0);for(int i 1; i n ;i){dp[i] dp[i-1] nums[i-1];}for(int i 1; i n ;i){if(dp[i-1] (dp[n] - dp[i]))return i-1;}return -1;}
};算法思路二:
既然我要算左边和右边的和是否相等, 那么我们不妨弄两个的dp数组, 一个前缀和一个后缀和, 对于前缀和我们只需要求出i之前的所有元素之和即可, 对于后缀和我们只需要求出i位置之后的所有元素之和即可, 但是注意细节我们需要考虑第一次计算会访问越界的情况, 所以我们需要提前把f[0]和g[n-1]这个位置处理好,而vector默认就为0. 编写代码:
class Solution {
public:int pivotIndex(vectorint nums) {int n nums.size();vectorint 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[i1] nums[i1];}for(int i 0; i n ; i){if(g[i] f[i]) return i;}return -1;}
};4. 除自身以外数组的乘积 算法思路:
有了上一题思路二的方法, 对于这道题我们不难解决, 只需求出对于i之前的前缀积以及对于i之后的后缀积即可, 遍历i位置此时answer[i]的位置就是f[i]*g[i], 但是注意细节,对于f[0]和g[n-1]我们要处理成1, 默认第一个位置之前的积为1,最后一个位置也是. 编写代码:
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint f(n),g(n),ret(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[i1] * nums[i1];for(int i 0; i n;i)ret[i] g[i] * f[i];return ret;}
};5. 和为k的子数组 算法思路:
首先我们肯定会想到暴力求解, 但是时间复杂度为O(N^2), 那可不可以使用双指针呢, 也就是我们的滑动窗口, 也不可以, 因为会有负数, 并没有单调性. 对于一个数组, 我们要求这个数组中和为k的子数组, 比如遍历到i位置, 我们要求i往前的和为k的子数组, 仅需从0位置查找, 找到和为sum[i] - k的子数组即可, 所以我们的前缀和思想又可以派上用场了.
首先我们先计算出前缀和, 但是我们并不需要创建一个前缀和数组, 仅需把每一次的结果记录到sum即可, 遍历一遍数组, 遍历到i位置就找i位置之前有没有sum nums[i] - k的, 我们可以把每一次的结果放到哈希表中, 但是注意我们并不需要i这个位置的和, 而是i之前的, 所以我们只保存i之前的前缀和即可, 如果有则ret,继续下一次查找, 但是注意如果整个数组等于k,也就是遍历到第一个位置我们需要在0到-1这个区间查找, 所以我们需要处理hash[0] 1. 编写代码:
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,int hash;int sum 0, ret 0;hash[0] 1;for(int i 0; i nums.size();i){sum nums[i];if(hash.count(sum - k)) ret hash[sum - k]; hash[sum];}return ret;}
};6. 和可被K整除的子数组 算法思路:
本道题依然不能使用滑动窗口来解决, 更上一道题思路类似, 只不过我们这道题哈希表里面存放的是sum的余数, 当遍历到i位置的时候只需要判断在i位置之前和除以k的余数是否等于sum除以k的余数, 因为同余定理, 可以看下图 也就是我们仅需在i位置前找到x%k等于sum%即可, 所以判断的时候我们需要判断sum的余数, 所以哈希表里面我们需要存放余数, 但是C中余数是由负数的, 负数和正数取余结果不一样, 所以我们需要进行修正. 使用sum遍历数组, 并且求出sum的余数r, 然后先判断sum之前的余数是否等于r, 如果等于则更新ret,最后将这个r也丢入到哈希表中. 编写代码:
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,int hash;hash[0 % k] 1;int sum 0, ret 0;for(int i 0; i nums.size() ; i){sum nums[i];int r (sum % k k) % k;if(hash.count(r)) ret hash[r];hash[r];}return ret;}
};7. 连续数组 算法原理:
这一道题没有单调性, 我们还是不能使用滑动窗口, 先把0修改成-1,我们就可以发现规律, i位置和在[0,i-1]位置的值相等, 即就能找到k数组, 因为正负抵消, 遍历到i位置我们判断该位置之前是否有和正好等于sum, 如果有则我们更新结果, 这里注意我们哈希表中需要存储下标, 因为结果需要我们求出长度, 如果有重复的sum, 我们只保存最早出现的那个下标.
class Solution {
public:int findMaxLength(vectorint nums) {unordered_mapint,int hash;hash[0] -1;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;}
};8. 矩阵区域和 算法思路:
首先读懂题意, 如下图所示, 也就是answer数组中的每一个位置就是mat当前位置的值向周围拓展k个单位元素的和.接下来进行分析 这道题要求我们求出拓展k个单位的和, 我们应该联想到一个算法, 二维前缀和dp.回忆一下二维前缀和的用法.如果说我们要求一个矩阵的前缀和数组, 则dp[ i ] [ j ] dp[ i - 1 ] [ j ] dp[ i ] [ j-1 ] - dp[ i - 1] [j - 1] arr[ i ] [ j ] 对于使用则有, 如果我们要求某一段区域的和, 则 ret dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] dp[x1-1][y1-1] 可以看出, 我们只要想求某段区域的和则前缀和数组中, 仅需知道这块区域的左上角下标个右下角下标即可,本题我们也可以用这样的思路, 但是有几个细节需要注意:
1, 注意我们创建dp数组时, 为了避免越界访问一般下标从1开始, 但是本题所给的数组mat是从下标0 开始, 所以我们它的dp数组需要稍作修改, 当时用到mat时, 将下标1处理 然后创建我们的ret数组, ret数组中的每一个位置我们都需要使用到dp数组, 所以需要求每一个位置的左上角位置与右下角位置的下标, 以便于正确的使用dp数组.根据下面我们求出该区域与使用dp数组的映射关系, 然后对于每一个位置分别求其结果. 编写代码:
class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size(), n mat[0].size();vectorvectorint dp(m 1,vectorint(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];}}vectorvectorint ret(m,vectorint(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,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;}
};完
