徐州建设企业网站,网站数据库是谁提供,深圳建网站seo,魏县专业做网站一)模板前缀和 【模板】前缀和_牛客题霸_牛客网 (nowcoder.com) 前缀和:快速的得出数组中某一段连续区间的和 暴力破解的话需要从头到尾的进行遍历#xff0c;时间复杂度就可以达到O(N)#xff0c;而前缀和时间复杂度是可以达到O(1)的 第一步:预处理创建出一个前缀和数组dp时间复杂度就可以达到O(N)而前缀和时间复杂度是可以达到O(1)的 第一步:预处理创建出一个前缀和数组dp这个数组和原始数组规模是同等大小的 dp[i]就表示从[1,i]区间内所有数组的和 1到N区间内的和和1到L-1区间内的和本质上来说是同一类问题研究问题的时候发现是同一类问题我们就可以把这同一类问题抽象成状态表示用动态规划的思想来进行解决 假设dp[3]表示的就是从1位置到3位置的所有元素的和就是14712 所以状态转移方程就是:dp[i]dp[i-1]array[i] 第二步:使用前缀和数组解决问题: dp[i]dp[r]-dp[l-1] 细节问题:在题干中下标为什么从1开始进行计数? 因为如果题目中给定的范围是0-2那么势必会访问到dp[-1]此时dp表就会出现下标越界访问的情况
public class Main {public static void main(String[] args) {
//1.输入数据Scanner scanner new Scanner(System.in);int nscanner.nextInt();int countscanner.nextInt();long[] arraynew long[n1];for(int i1;in;i){array[i]scanner.nextLong();}
//2.预处理一个前缀和数组long[] dpnew long[n1];for(int i1;in;i){dp[i]array[i]dp[i-1];}
//3.使用前缀和数组while(count0){count--;int leftscanner.nextInt();int rightscanner.nextInt();System.out.println(dp[right]-dp[left-1]);}}
} 二)二维前缀和 【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com) 一)预处理出来一个前缀和矩阵:这个前缀和矩阵必须和原始矩阵规模大小是一样的 dp[i][j]表示从(11)这个位置到(ij)这段区间内所围成的矩形的这段区间内所有元素的和 dp[i][j]dp[i-1][j]array[i][j]dp[i][j-1]-dp[i-1][j-1] resultdp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1] 自己画图可以不花正方形可以直接画数进行分析 import java.util.Scanner;
import java.util.Arrays;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {
//1.先进行处理数据的输入Scanner scannernew Scanner(System.in);int mscanner.nextInt();int nscanner.nextInt();int countscanner.nextInt();//初始化输入次数long[][] arraynew long[m1][n1];for(int i1;im;i){for(int j1;jn;j){array[i][j]scanner.nextInt();}}
//2.创建dp表进行填表,使用前缀和数组
long[][] dpnew long[m1][n1];for(int i1;im;i){for(int j1;jn;j){dp[i][j]dp[i-1][j]array[i][j]dp[i][j-1]-dp[i-1][j-1];}}
//2.进行返回结果,使用前缀和数组while(count0){int x1scanner.nextInt();int y1scanner.nextInt();int x2scanner.nextInt();int y2scanner.nextInt();
long resultdp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1];
// System.out.println(Arrays.deepToString(dp));System.out.println(result);count--;
}}
} 三)寻找数组的中心下标 724. 寻找数组的中心下标 - 力扣Leetcode 暴力枚举:每一次枚举一个中间下标i的时候都需要把(0-i-1)之间的数进行相加还需要把(iarray.length)之间的数进行相加一遍可见时间复杂度会变得非常的高 一)定义一个状态表示: f[i]表示从0号位置到i-1位置所有元素的和 g[i]表示从i1号位置到n-1位置所有元素的和 二)根据状态表示推导状态转移方程 f[i]f[i-1]array[i-1] g[i]g[i1]array[i1] 三)初始化(防止发生数组越界) f[0]0g[n-1]0 四)填表顺序: f表:从左向右 g表:从右向左 class Solution {public int pivotIndex(int[] array) {int narray.length;int[] fnew int[n];//f[i]表示从0号位置到i位置数组中这段区间内的和int[] gnew int[n];//g[i]表示从i1号位置到n-1位置数组中这段区间的和//最后只是需要得出f[i]g[i]即可f[0]0;//填写到f[0]位置的时候数组就会发生越界g[n-1]0;//因为填写到n-1位置的时候数组就会发生越界for(int i1;in;i){//f从前向后进行填表f[i]f[i-1]array[i-1];}for(int in-2;i0;i--){//g从后向前填表g[i]g[i1]array[i1];}for(int i0;in;i){if(f[i]g[i]){return i;}}return -1;}
} 四)除自身以外数组的乘积: 238. 除自身以外数组的乘积 - 力扣Leetcode 一)定义一个状态表示: f[i]表示从0-i-1位置这段区间所有元素的乘积 g[i]表示从i1位置开始到n-1这段区间内所有元素的乘积 二)根据状态表示推导状态转移方程: f[i]f[i-1]*array[i-1](0号位置的元素到i-2位置的元素的乘积再乘上array[i-1]位置的元素即可) g[i]g[i1]*array[i1](从i2号位置的元素到n-1号位置的元素的乘积再乘以i1号位置的元素) 三)进行初始化操作:f[0]1g[n-1]1 四)填表顺序:f表从左向右填g表从右向左填 class Solution {public int[] productExceptSelf(int[] array) {
//1.创建前缀积以及后缀积数组int[] fnew int[array.length];int[] gnew int[array.length];int[] retnew int[array.length];f[0]1;g[array.length-1]1;
//2.初始化for(int i1;iarray.length;i){f[i]f[i-1]*array[i-1];}for(int iarray.length-2;i0;i--){g[i]g[i1]*array[i1];}for(int i0;iarray.length;i){ret[i]f[i]*g[i];}return ret;}
} 五)和为K的子数组 剑指 Offer II 010. 和为 k 的子数组 - 力扣Leetcode 是列出连续子数组 1)暴力解法: 1)采取枚举策略定义两个变量i和ji每次固定不动j一直向后走走一步加array[j]直到遇到sum和等于k因为我们可以使用N^2的时间复杂度将所有子数组枚举出来 2)但是此时j应该继续向后走直到j把整个数组遍历完成因为有可能会出现j遇到整数又遇到负数的情况此时应该还是让sumsumarray[j]如果sumk应该再次让count)此时的时间复杂度就是O(N^2)中心思路是找到以某一个位置为起点的子数组 不能使用双指针优化:必须有单调性 如果left到左箭头之间的和和right到右箭头之间的和是等于0的因为right指针还是不断地向右进行移动也就是说双指针会漏掉中间的这种情况 class Solution {public int subarraySum(int[] array, int k) {int count0;for(int i0;iarray.length;i){int sum0;for(int ji;jarray.length;j){sumsumarray[j];if(sumk) count;}}return count;}
} 2)前缀和:快速的求出某一段区间的和 2.1)先找到以i位置为结尾的所有子数组(一定是包含i位置的元素的)先找到和为K的以i位置为结尾子数组有多少个然后把所有情况都进行累加起来 2.2)从而就转化成了在[0~i-1]区间内i前面有多少个前缀和等于sum[i]-k 2.3)找到所有以i为结尾的子数组中有多少和是等于sum[i]-k的就相当于是找到从0到i区间内的一个位置使得[0j-1]位置的和等于sum[i]-k那么此时求的不就是前缀和dp[j-1]吗 1)如果真的采用上面的思路进行遍历查找[0-i]区间内有多少前缀和等于sum[i]-Ki下标需要从头到尾进行遍历一遍每一次遍历i下标的时候还需要从前缀和数组中从0-i位置进行遍历有看看有多少前缀和等于sum[i]-k的此时就可以使用哈希表来进行记录0-i-1这段区间内的前缀和这样绿线的部分直接就可以通过哈希表一次直接遍历出蓝色线的部分也就是直接可以求出有多少前缀和 2)那么最终的时间复杂度就是O(N^2)K时间复杂度又会飙升 3)前缀和哈希表 class Solution {public int subarraySum(int[] array, int k) {//dp[i]表示从0号位置到i号位置所有元素的和,开始初始化dp数组int[] dpnew int[array.length1];dp[0]0;for(int i1;iarray.length;i){dp[i]dp[i-1]array[i-1];}System.out.println(Arrays.toString(dp));int count0;//1.使用前缀和注意下标的映射关系
//2.注意新的dp数组left到right区间内的和有多少等于k是dp[right]-dp[left-1]是[left,right]区间内的和for(int left1;leftarray.length;left){for(int rightleft;rightarray.length;right){if(dp[right]-dp[left-1]k) count;}}return count;}
} 使用哈希表来进行解决HashIntIntkey存放的是前缀和Value存放的是前缀和出现的次数就不需要每一次从0位置到i-1位置来进行查找前缀和有多少等于sum-k的了只需要统计前缀和出现的次数即可如果发现sum[j]sum[i]-k了那么从j1位置到i位置的这段区间内和就等于k 1)前缀和加入哈希表的时机: 第一种方式就是将前缀和全部计算出来然后把前缀和一股脑地全部加入到哈希表中然后从0号位置到i号位置一直进行遍历查找前缀和等于sum[i]-k的这会出现重复的情况可能会统计到i位置之后的前缀和等于sum[i]-k的值可能会出现重复但是我们是来查询i前面的前缀和等于sum[i]-k的 再进行计算i位置之前哈希表中只是保存[0i-1]位置之间的前缀和 2)不用真的创建一个前缀和数组: 只需要使用sum来标记前一个位置的前缀和 3)如果整个前缀和等于K 当进行第一次枚举到i位置的时候发现从0号位置到i位置数组的和是等于k的那么此时就需要从[0-1]区间内找一个前缀和等于0的位置这显然是不存在的所以应该提前加入到hash表中hash01就是为了避免这种情况被漏掉所以先把(01)加入到哈希表中 class Solution {public int subarraySum(int[] nums, int k) {HashMapInteger,Integer resultnew HashMap();result.put(0,1);int count0;int sum0;for(int i0;inums.length;i){sumsumnums[i];//记录当前位置的前缀和countcountresult.getOrDefault(sum-k,0);result.put(sum,result.getOrDefault(sum,0)1);}return count;}
} 六)和可被 K 整除的子数组 974. 和可被 K 整除的子数组 - 力扣Leetcode 1.暴力破解:找出所有前缀和(left到right区间可以被k整除的和那么left到right区间内的和就可以被k整除) class Solution {public int subarraysDivByK(int[] array, int k) {int narray.length;int[] dpnew int[n1];dp[0]0;for(int i1;iarray.length;i){dp[i]dp[i-1]array[i-1];}int count0;for(int left1;leftarray.length;left){for(int rightleft;rightarray.length;right){int tempdp[right]-dp[left-1];if(temp%k0) count;}}return count;}
} 2.暴力破解:找到所有的子数组找出和能被k整除的 class Solution {public int subarraysDivByK(int[] array, int k) {int count0;for(int i0;iarray.length;i){int sum0;for(int ji;jarray.length;j){sumsumarray[j];if(sum%k0) count;}}return count;}
} 3.前缀和: 1)同余定理: 1)sum[i]是从0号位置开始到i号位置开始所有元素的和正好找到j位置使(sum[i]-x)%k0 (sum[i]-x)/kt.......0 2)所以说这个题就转化成了从0到i-1区间内找到有多少个前缀和的余数等于sum%k (sum%kk)%k(哪一个区间i前面的数的所有和%ksum[i]%k) 3)创建一个哈希表:key是前缀和的余数value是这个前缀和对应的出现的次数 lass Solution {public int subarraysDivByK(int[] array, int k) {HashMapInteger,Integer resultnew HashMap();result.put(0,1);int count0;int sum0;for(int i0;iarray.length;i){sumsumarray[i];countresult.getOrDefault((sum%kk)%k,0);result.put((sum%kk)%k,result.getOrDefault((sum%kk)%k,0)1);}return count; }
} 七)连续数组: 525. 连续数组 - 力扣Leetcode 算法原理: 1)将所有的0全部变成-1然后求整个数组的和是0的最大子数组长度 2)在数组中找出最长的子数组使子数组中所有元素的和等于0 细节问题: 1)哈希表中存什么 hashint,intkey值存放的是前缀和value值存放的是前缀和所对应的下标 2)什么时候存入到哈希表 使用完成之后丢入到哈希表 3)如果有重复的sum[i]怎么进行存放呢 只是保留前面的那一对i的值越靠近左边越好 4)默认有前缀和等于0的情况如何进行处理 hash[0]-1 5)长度怎么算 i-j1-1i-j class Solution {public int findMaxLength(int[] array) {for(int i0;iarray.length;i){if(array[i]0) array[i]-1;}int count0;int sum0;HashMapInteger,Integer mapnew HashMap();
//第一个位置存放的是前缀和,第二个位置存放的是下标,最终maxlen里面存放的是长度int maxlen0;map.put(0,-1);
//如果从0到i位置的元素和已经等于0了,那么此时就是在0到-1区间内寻找和是0的数组,此时长度就是i-01,所以要存放0,-1for(int i0;iarray.length;i){sumsumarray[i];if(map.containsKey(sum)){maxlenMath.max(maxlen,i-map.get(sum));}else{map.put(sum,i);
//如果哈希表中已经存在sum了,就不需要再次进行存放了
//因为我们所需要进行寻找的是长度最大的数组} }return maxlen;}
} 八)矩阵区域和 1314. 矩阵区域和 - 力扣Leetcode 如下图所示我们要求的中心下标的矩形面积是二维前缀和 (xkyk)所围成的正方形的面积-(x-ky-k)所围成的正方形的面积 class Solution {public int[][] matrixBlockSum(int[][] array, int k) {int colarray[0].length;int rowarray.length;int[][] dpnew int[row1][col1];int[][] resultnew int[row][col];
//1.初始化二维前缀和,注意下标的映射关系for(int i1;irow;i){for(int j1;jcol;j){dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]array[i-1][j-1];}}System.out.println(Arrays.deepToString(dp));
//2.计算最终矩阵的值,注意下标的映射关系for(int i0;irow;i){for(int j0;jcol;j){int x1Math.max(i-k,0)1;int y1Math.max(j-k,0)1;int x2Math.min(ik,row-1)1;int y2Math.min(jk,col-1)1;result[i][j]dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]dp[x1-1][y1-1];}}return result;}
}
