分类网站模板,ssr网站开发,做网站镜像步骤,品牌网站建设3a小蝌蚪题目一#xff1a; 算法原理#xff1a; 这道题是一维前缀和的模板题#xff0c;通过这道题我们可以了解什么是前缀和
题意很简单#xff0c;就是先输入数组个数和查询次数#xff0c;然后将数组的值放进数组#xff0c;每次查询给2个数#xff0c;第一个是起点#x…题目一 算法原理 这道题是一维前缀和的模板题通过这道题我们可以了解什么是前缀和
题意很简单就是先输入数组个数和查询次数然后将数组的值放进数组每次查询给2个数第一个是起点第二个是终点打印这个区间的和
稍微需要注意的是这里的数组存放是从下标1开始的而不是从下标0开始至于为什么等到后面讲前缀和的时候就知道了
老规矩先用暴力解决根据题意用循环来累加起点到终点的和就是将题目的要求转化成代码所以很简单但是时间复杂度是On*q因为每次查询都需要遍历一次数组最坏的情况就是q次每次都从1到n求和所以是On*q
而题目中数据范围nq最高来到了10^5所以On*q的时间复杂度来到了10^10一定会超时
接下来就采用前缀和的方法来解决这道题
前缀和分为两步
第一步创建前缀和数组dp下标中对应的值等于另一个数组下标前的所有值之和
第二步使用前缀和数组
比如第一步 创建 dp时就是将原数组arr进行累加
dp1下标就是arr1下标的和dp2下标就是arr1下标2下标的和dp3下标就是arr1下标2下标3下标的和如此类推
当然到第三个之后就不用傻乎乎的又从头加到尾只需要拿dp数组的前一个值加上当前arr对应的值即可
接下来是第二步 根据题意需要我们找到L到r区间的和那么我们就可以用r之前的和减去L之前的和也就是作差值就能得到L到r的和
而又因为我们已经在前缀和数组中存储好了r之前的和以及L之前的和之间拿来用即可这里的时间复杂度就是O1
转化为代码形式就是dp[r]-dp[l-1]
所以综上使用前缀和的算法就能将时间复杂度降为OqOn
其中Oq是进行q次查询每次查询的时间复杂度都是O1
On是在创建前缀和数组时遍历原数组的值
这也是前缀和数组解决的问题用来快速计算一段连续区间的和
代码1
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);//输入n和qint nin.nextInt();int qin.nextInt();//创建原数组并放进去int[] arrnew int[n1];for(int i1;in;i){arr[i]in.nextInt();}//创建前缀和数组并计算long[] dpnew long[n1];for(int i1;in;i){dp[i]dp[i-1]arr[i];}//查询q次while(q0){//输入查询区间的l和rint lin.nextInt();int rin.nextInt();//使用前缀和数组System.out.println(dp[r]-dp[l-1]);//次数-1q--;}}
}
注其中在创建前缀和数组的时候因为原数组的值最大来到了10^9所以避免累加的时候溢出我们选择用long来防溢出
题目二 算法原理 就是从刚刚存储一维数组的之前所有元素的和的前缀和数组变为了存储二维数组的矩阵和的前缀和数组
相较一维二维要更抽象一点但是只要画图还是很好理解的
仍然是先暴力也没有什么难的就是从x1y1开始遍历直到x2y2
而最坏的情况下就是遍历整个二维数组即要遍历m行n列总共q次
所以时间复杂度Om*n*q
由数据范围可知很容易超时
所以要采用二维前缀和
仍然分为两步
第一步创建二维前缀和数组
第二步使用二维前缀和数组
先说第一步
二维前缀和存储的是以11为左上角该位置为右下角的矩阵和所以画图如下 根据一些简单的数学面积计算很容易得到这个公式
所以在创建二维前缀和的时候直接用这个公式进行赋值即可
然后第二步
有了二维前缀和数组接下来要解决的就是如何计算x1y1作为左上角到x2y2作为右下角之间的矩阵和还是画图如下 也是根据简单的数学面积计算就能得到这个公式
所以二维前缀和并不难运用的知识几乎就只是小学数学最多初中数学的水平难度只不过就是将这个数学知识转化为代码形式而已
代码1
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int nin.nextInt(),min.nextInt(),qin.nextInt();int[][] arrnew int[n1][m1];long[][] dpnew long[n1][m1];//将数据放进数组for(int i1;in;i){for(int j1;jm;j){arr[i][j]in.nextInt();}}//创建二维前缀和数组for(int i1;in;i){for(int j1;jm;j){//公式dp[i][j]dp[i][j-1]dp[i-1][j]-dp[i-1][j-1]arr[i][j];}}//查询q次while(q0){int x1in.nextInt(),y1in.nextInt(),x2in.nextInt(),y2in.nextInt();//公式System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]);q--;}}
}
注也是在创建二维前缀和数组的时候由于原数组的值比较大有可能累加求和的过程中溢出所以用long来防溢出
题目三 算法原理 先用暴力遍历整个数组每遍历到一个下标就循环求前面的和以及后面的和如果相等则找到了中心下标返回该下标即可时间复杂度为ON^2
接下来就是优化因为题目中出现连续区间求和所以要联想的前缀和的算法
依旧分为两步创建前缀和数组和使用前缀和数组
第一步创建前缀和数组
因为是一维前缀和所以之间按照模板思路去创建即可只不过这里下标是从0开始的所以前缀和的值是不包括当前元素的前面所有元素的和
比如nums[1,7,3,6,5,6]
创建前缀和数组就为
dp[0,1,8,11,17,22,28]
第二步使用前缀和数组
根据规律很容易找到这个公式
dp[i]dp[nums.length]-dp[i1]
转化为人话就是左边的和等于右边的和
所以很简单的就解决了这个题目时间复杂度为O2N也就是ON
代码1
class Solution {public int pivotIndex(int[] nums) {int nnums.length;//不管会不会溢出用long保险long[] dpnew long[n1];//创建前缀和数组for(int i1;in;i){dp[i]dp[i-1]nums[i-1];}//使用前缀和数组for(int i0;in;i){if(dp[i]dp[n]-dp[i1]){return i;}}//没找到return -1;}
}
然后这里还可以采用前缀和以及后缀和两个数组来解决 这也是一种前缀和算法因为本质都是预处理什么是后缀和很简单就是从后往前记录后面的和比如i位置前缀和是存i之前所有元素的和那么后缀和就是存i之后所有元素的和
其实跟我们上面那个解法唯一的区别就是在dp[i]dp[nums.length]-dp[i1]这个公式中我们用dp[nums.length]-dp[i1]代表了后缀和所以我们可以用后缀和数组来记录这里的值 通过画图很容易找到这个公式
而且这里就没有必要创建n1长度的前缀数组和后缀数组了因为当in-1时前缀和里面就已经不包括i这个位置的数了没必要
接下来就是使用前缀和数组和后缀和数组
那就是遍历整个数组如果该位置的前缀和等于后缀和那么就返回该位置 代码2
class Solution {public int pivotIndex(int[] nums) {int nnums.length;//创建前缀和数组dp1和后缀和数组dp2long[] dp1new long[n];long[] dp2new long[n];//构建前缀和数组for(int i1;in;i){dp1[i]dp1[i-1]nums[i-1];}//构建后缀和数组for(int in-2;i0;i--){dp2[i]dp2[i1]nums[i1];}//使用前缀和数组和后缀和数组for(int i0;in;i){if(dp1[i]dp2[i]){return i;}}//没找到return -1;}
}
题目四 算法原理 题意很简单就是返回除该位置的值的其他元素的乘积并用数组保存
第一反应先用暴力那就是遍历整个数组除了等于该位置时其他全部都乘一下保存到数组里时间复杂度为ON^2不满足题目要求的ON
这里题目也很明确提示了用前缀和算法其中后缀就是从后往前记录本质与前缀一样的
只不过这道题是用乘法也就是说应该叫做前缀积后缀积
那么每遍历到一个数只需要用该位置的前缀积*后缀积即可
那么现在就是来到第一步创建前缀后缀数组
之前前缀和数组我们都默认让0下标为0因为是求和所以不希望干扰其他元素之和所以用0而这道题是求积所以应该让0下标为1这样1*任何数还是任何数所以这里稍微要转换一下思路
这里前缀积长度只用设置跟原数组长度一样即可因为跟上道题一样因为到第一个元素/最后一个元素前缀积/后缀积本来就不包括这个元素没必要 还是通过画图很容易得到这两个公式
几乎和上道题的第二种解法一模一样的就是加换成了乘 然后就是使用前缀积数组和后缀积数组遍历整个数组只需让该位置的前缀积乘后缀积让这个值保存到要返回的数组里即可 nn
代码1
class Solution {public int[] productExceptSelf(int[] nums) {int nnums.length;//创建前缀积数组dp1和后缀积数组dp2int[] dp1new int[n];int[] dp2new int[n];//这里需要稍微修改一下dp1[0]dp2[n-1]1;//构建前缀积数组for(int i1;in;i){dp1[i]dp1[i-1]*nums[i-1];}//构建后缀积数组for(int in-2;i0;i--){dp2[i]dp2[i1]*nums[i1];}//要返回的数组int[] retnew int[n];//使用前缀积数组和后缀积数组for(int i0;in;i){ret[i]dp1[i]*dp2[i];}return ret;}
}
注题目注明了积不会超过32位整数也就是int的范围所以用int即可
也许你有一点疑问上一道题可以只用前缀和就能解决这道题能不能也只用前缀积解决呢其实不太可以虽然我们把上道题的减换成除即dp[i]dp[nums.length]/dp[i1]首先是题目要求了不能使用除法虽然投机取巧说我学过表示除法但是当除数为0时也行不通所以这道题基本不能只用前缀积解决
但是前缀加后缀这个方法也不难也很好理解所以不要排斥多一种方法就越好
题目五 算法原理
题意很简单就是找数组中有多少个和为k的子数组
先用暴力看看大致流程是怎么个事
第一层循环遍历整个数组每遍历到一个位置就以该位置作为子数组的起始位置然后第二层位置从该位置开始往后遍历直到数组最后一个元素这样就枚举了所有子数组的情况
用一个变量记录当前子数组的和如果等于返回值就1
这就是暴力枚举时间复杂度为ON^2空间复杂度为O1
然后就来想优化我们之前做过一道题也是求和为k的子数组个数在那一道题我们使用的是滑动窗口这一道题好像跟那道题一模一样但其实有一点区别那就是之前那道题中数组的值全是正数那么就具有单调性而这道题的提示中写了数组中的值有正有负所以就不能保证右边界往右滑动时是递增的左边界往右滑动时是递减的不具有单调性所以这道题不能使用滑动窗口
但是看到子数组之类的也要反应出来滑动窗口算法至于能不能用再分析不能看到子数组却想不到滑动窗口
既然滑动窗口不行然后就该继续思考这道题又出现求数组的和那么就该想到前缀和至于能不能用就来分析
如果我们创建了一个前缀和数组那么接下来就是遍历前缀和数组如果有等于k的返回值就1
但是这样统计不全比如示例[1,2,3]k3
创建前缀和数组为[0,1,3,6]
遍历完前缀和数组有一个3那么就返回1那么这样就忽略了6-33这个区间的子数组因为我们创建的前缀和数组是默认以第一个元素作为子数组起始位置的
那么接下来我们就要思考怎么找到6-33这个区间的子数组如果又想到遍历前缀和数组每遍历一个位置就将该位置作为前缀和数组的起始位置那么就又绕回了暴力解法了甚至还不如暴力解法还多了前缀和创建的时间复杂度ON变成ON^2N
那么如何不通过遍历就能找到子数组呢这里我们就要改变一下思路我们之前都是先把整个前缀和创建出来再分析现在我们每添加一个前缀和的时候就来分析 我们每添加到i位置的前缀和sum时就往前面找如果前面的前缀和有一个sum-k那么就说明后面就有一个为k的子数组同理有两个前缀和为sum-k那么就说明有两个为k的子数组如上图
那么怎么保存有多少个前缀和为sum-k的个数呢是不是就想到哈希表了专门用来记录出现次数的
所以这道题就是采用前缀和哈希表来解决
而且这道题其实不能真正创建一个前缀和数组因为我们是一个一个来分析的不需要预处理全部前缀和所以只需要用一个变量记录当前前缀和然后到下一个就更新前缀和
还有如果整个区间为k那么sum-k0而此时没有0对应的次数但是这种情况又算作一个所以这时哈希表应该提前put01解决这种问题
代码1
class Solution {public int subarraySum(int[] nums, int k) {//创建哈希表HashMapInteger,Integer mapnew HashMap();//准备工作map.put(0,1);//sum为记录当前的前缀和count为有多少个和为k的子数组int sum0,count0;//遍历数组for(int x:nums){//记录当前前缀和sumx;//找前面有多少个前缀和为sum-k的子数组countmap.getOrDefault(sum-k,0);//更新该位置的前缀和数组到哈希表中map.put(sum,map.getOrDefault(sum,0)1);}//返回个数return count;}
}
虽然代码很少但是挺难想的需要先找到用前缀和数组然后采用一步一步来分析最后通过哈希表来解决分析中的问题需要多积累经验
题目六 算法原理
这道题是某一届蓝桥杯的原题所以完全可以自己先模拟竞赛完成这道题
第一反应当然是暴力无论后面想没想到后面前缀和哈希表的方法但是总能通过大部分用例
仍然是两层循环来枚举出所有子数组的情况然后继续判断如果此时的子数组的和能被k整除那么就返回值1
代码1暴力
class Solution {public int subarraysDivByK(int[] nums, int k) {int count0;//暴力枚举所有子数组for(int i0;inums.length;i){int sum0;for(int ji;jnums.length;j){sumnums[j];//如果子数组能被整除if(sum/k((float)sum)/k){//计数器加1count;}}}//返回计数器return count;}
}
很简单就完成了这道题用时几乎不超过5分钟
虽然没能全部通过但是也能通过大部分的用例68/76 而蓝桥杯的赛制是过多少案例点就给部分分的不是全过就给满分没全过就0分的赛制所以在竞赛中完全可以先暴力后面剩余时间再来想优化
然后就是用前缀和哈希表来解决这道题这道题跟上一道几乎一模一样就是一个是和为k一个是和能被k整除所以大致步骤和细节都是一样的就不赘述了
但是这里有两点小细节是上一道题没有的
第一点我们上一道题是找之前前缀和中有多少个为sum[i]-k的个数那么这道题我们要找的是前缀和的余数中有多少个为“什么”的个数
这里有个定理叫做同余定理
公式a-b/ p k …… 0 a%kb%k
比如26-12/ 7 2 …… 0
所以26%712%7 5 证明过程如上简单来说就是我们还知道ap*k%pa%p这个道理
那么我们将a-b/ pk进行左右移项再加上同余即可得到a%pb%p 所以回到我们题目 此时前缀和为sum我们假设有一个区间为k那么后面这个区间sum-k如果能被k整除那么就找到一个
所以用同余定理即可得到我们要找的是前缀和的余数中有多少个为sum%k的个数就能说明前面有多少个能被k整除的子数组 第二点
java中负数%正数如何修正的问题因为这道题也是存在正负数的所以sum的值也可能为负数
比如[-1,2,9]k2
按照思路哈希表应该存有01
然后往后遍历sum%k -1%2-1发现哈希表没有-1的键返回值不变
哈希表就加上-11
然后继续遍历sum%k 1%2 1发现哈希表没有1的键返回值不变
哈希表就加上11
到这里发现不对的地方了吧明明出现了[2]这个子数组但是返回值却没有加1
按照图上所示我们代值画图即可 在数学中-1%21即取模的值都为正数而在Java中-1%2-1所以这个是有矛盾的点因此我们要将Java中取模操作后的值进行负转正也就是统一返回正数
那么我们就可以sum%k变为sum%kk%k因为题目中k是恒大于等于2的而sum%k一定比
-k大所以加上k后一定是大于0的因此再%k返回的就一定是正数
接下来就是按照上道题的代码进行细节添加即可
代码1
class Solution {public int subarraysDivByK(int[] nums, int k) {//创建哈希表HashMapInteger,Integer mapnew HashMap();//准备工作map.put(0,1);//sum为记录当前的前缀和count为有多少个和能被k整除的子数组int sum0,count0;//遍历数组for(int i0;inums.length;i){//记录当前前缀和sumnums[i];//找前面有多少个前缀和为sum%k的子数组countmap.getOrDefault((sum%kk)%k,0);//更新该位置的前缀和的余数数组到哈希表中map.put((sum%kk)%k,map.getOrDefault((sum%kk)%k,0)1);}//返回数目return count;}
}
主要要知道有同余定理以及数学中负数求余的值也为正数Java取余统一正负的操作
题目七 算法原理
题意很简单就是找到最长的连续子数组这个子数组0和1的数量相等 那么怎么判断0和1是否相等呢其实可以像题目五求和为k的子数组的方式来求比如找到和为长度一半的子数组就除2这样也可以但是因为是只有01两种情况那么如果让0为-1那么就变成简单的和为0的子数组这样就可以找到题目要求的子数组
然后就是按照和为k的子数组的流程来解决了只是那道题是找有多少个而这道题是求最长的子数组长度所以在哈希表中存的就不是个数了而应该是下标
然后就是如果出现重复的哈希值是否要更改在之前那一道题的时候因为要求个数所以每找到一个就要更新对应的个数但是这一道题哈希表对应下标也要更改吗这里要好好分析一下很细节的问题 比如遍历到j下标时存了当前的sum值然后遍历到i下标时发现又为sum那么此时就找到一个子数组的和为0即j到i这个子数组这时如果更新下标则为i不更新则为j 然后如果后面又出现和为sum的子数组情况就很明了了我们要更长的子数组那么肯定要j到k这个子数组也就是左边界越靠左越好所以答案是不更新
还有一个小问题就是初始化之前那道是初始化解决整个数组和为k则sum-k为00对应的哈希值则应该为1代表这种情况有一个符合要求的子数组
而这里假设就是[0,1]这个数组按理来说遍历到1这里此时sum为0而哈希表里没有0这个key则长度应该为下标1-而这个对应的就应该是0这个key对应的值很明显长度是2所以应该为-1所以初始化时应该加入0-1这对哈希
代码1
class Solution {public int findMaxLength(int[] nums) {HashMapInteger,Integer mapnew HashMap();int len0;int sum0;//初始化map.put(0,-1);//遍历for(int i0;inums.length;i){//如果是0就加-1是1就加1sum(nums[i]0?-1:1);//如果找得到key为sumif(map.containsKey(sum)){//更新答案为更长的但是不更新哈希表lenMath.max(len,i-map.get(sum));}else{//没找到则更新哈希表map.put(sum,i);}}//返回答案return len;}
}
题目八 算法原理
题意不是很好理解得一点一点看着题目的公式和要求画图来理解才大致知道输出答案的得到流程
根据公式一点一点套能得到答案但是在画图上直观简单来说就是扩大k圈后其中所有的和 比如示例1中输出数组的第一个12就是像上面这样得来的即1245超出边界的就按0处理 再来一个比如第二个21就是像上面这样得来的即123456同样超出边界就按0处理
这些就是k1即扩大1圈的样子同理k2就扩大两圈再求里面的和
题目终于理解了那么接下来就是解决问题
暴力那就是一个一个遍历加太笨了而且时间复杂度很高因为是二维数组所以基本都是以m*n为底的多少次方这种时间复杂度了
也是求和那么就该想到前缀和又是二维的那么就该用二维前缀和
回顾一下二维前缀和
分为两步创建前缀和数组使用前缀和数组
创建前缀和数组画图就完事了然后公式看图推 就是这一整块 上面一大块 左边一大块 - 多加了一次的A 这一次要求和的D
使用前缀和数组画图就完事了然后公式看图推 得知左上角x1y1和右下角x2y2求这个范围的矩阵和
就是 D 整一大块 - 上面一大块 - 左边一大块 多减了一次的A
同时注意我们二维前缀和都是从11开始也就是说实际是下面这样就可以避免讨论边界情况即上面出现[x1-1]或者[y1-1]等当x1y1等于0这一系列的边界讨论而以11作为起点就可以不用讨论边界情况默认空的为0 那么这道题就变得很简单了返回的数组中每一个对应ij值加或者减k即可得到左上角x1y1和右下角x2y2
只不过如果越界了那么就默认以原数组的边界作为界
那么这时候你就想说那又要分类讨论又要各种ifelse还是太绕了有没有更简单更无脑的方法呀
有的兄弟有的我们只需要求左上角时i-k和j-k与0求max即可同理求右下角时ik或jk与行数m-1或列数n-1求min即可如下图 最后套用公式即可
大致流程就是如上了 但是有一个小细节那就是原数组是从00开始的与第二题的原数组从11开始不一样那怎么办呢
其实我们只需要给他加或者减1即可即在创建二维前缀和时加上的那一小块其实对应原数组要减1 而在使用二维前缀和时x1y1x2y2其实等于原数组加1 简单的变化关系就是
前缀和数组——原数组要减1
原数组——前缀和数组要加1
原因就是前缀和数组是从11开始的而原数组是从00开始的就导致前缀和数组比原数组要多一行多一列导致下标也多1
代码1
class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {//m是行数n是列数int mmat.length;int nmat[0].length;//创建前缀和数组int[][] dpnew int[m1][n1];for(int i1;im1;i){for(int j1;jn1;j){//前缀和数组要用原数组要减1dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]mat[i-1][j-1];}}//创建要返回的二维数组int[][] ansnew int[m][n];//使用前缀和数组for(int i0;im;i){for(int j0;jn;j){//原数组变到前缀和数组要加1int x1Math.max(0,i-k)1;int y1Math.max(0,j-k)1;int x2Math.min(m-1,ik)1;int y2Math.min(n-1,jk)1;ans[i][j]dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]dp[x1-1][y1-1];}}return ans;}
}
综上基础中等的前缀和算法就学完啦总结就是看见题目有求和则要想到前缀和步骤为两步创建和使用其中公式不要死记硬背画图现场推很快的
