关于算法:leetcode数组算法前缀和构建和应用

<article class=“article fmt article-content”><h2>leetcode——数组算法——前缀和构建和利用</h2>前缀和技巧实用于疾速、频繁地计算一个索引区间内的元素之和<h3>303. 区域和检索 - 数组不可变</h3>比方leetcode 303. 区域和(检索 - 数组不可变)题目介绍：给定一个整数数组 <code>nums</code>，解决以下类型的多个查问:<ol><li>计算索引 <code>left</code> 和 <code>right</code> （蕴含 <code>left</code> 和 <code>right</code>）之间的 <code>nums</code> 元素的 和 ，其中 <code>left <= right</code></li></ol>实现 <code>NumArray</code> 类：<ul><li><code>NumArray(int[] nums)</code> 应用数组 <code>nums</code> 初始化对象</li><li><code>int sumRange(int i, int j)</code> 返回数组 <code>nums</code> 中索引 <code>left</code> 和 <code>right</code> 之间的元素的 总和 ，蕴含 <code>left</code> 和 <code>right</code> 两点（也就是 <code>nums[left] + nums[left + 1] + … + nums[right]</code> )</li></ul>示例 1：<pre><code>输出：[“NumArray”, “sumRange”, “sumRange”, “sumRange”][[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]输入：[null, 1, -1, -3]解释：NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))</code></pre><h4>解法一：</h4>1.在sumRange外面，for循环从left到right遍历nums，用一个变量记录。代码如下：<pre><code class=“java”>class NumArray { //类里必定有一个int[]成员 private int[] myArray; public NumArray(int[] nums) { this.myArray=nums; } public int sumRange(int left, int right) { int result=0; if(left>right||left<0||right>myArray.length){ return 0; } //myArray[left]始终加到myArray[right] for(int i=left;i<=right;i++){ result+=myArray[i]; } return result; }}</code></pre><blockquote>如果屡次调用sumRange，会始终反复计算。</blockquote><h4>解法2</h4>2.在构造函数中，结构一个对于nums的前缀和数组preNums，preNums[i]的值就是nums前i项的和。Q：如何结构这个前缀和数组？A：前缀和数组的每一项 = 前一项（前i-1项的和）+ nums[i]。<blockquote>留神：因为前缀和数组的表白意义应该是前1项的和，前2项的和；而没有个前0项的和。所以这里将preNum[0]=0；目标是更合乎咱们的表白语义。比方preNum[1]就是nums前1项的和。</blockquote>代码如下：<pre><code class=“java”>class NumArray { public int[] getPreArray() { return preArray; } //记录一个前缀和数组，防止sumRange反复的for private int[] preArray; public NumArray(int[] nums) { preArray = new int[nums.length + 1]; // 计算 nums 的累加和 for (int i = 1; i < preArray.length; i++) { preArray[i] = preArray[i - 1] + nums[i - 1]; } } public int sumRange(int left, int right) { int result=preArray[right+1]-preArray[left]; return result; }}</code></pre><h3>304. 二维区域和检索 - 矩阵不可变</h3>如果是二维数组的前缀和如何构建和应用呢？比方leetcode 304. 二维区域和检索 - 矩阵不可变给定一个二维矩阵 <code>matrix</code>，以下类型的多个申请：<ul><li>计算其子矩形范畴内元素的总和，该子矩阵的 左上角 为 <code>(row1, col1)</code> ，右下角 为 <code>(row2, col2)</code> 。</li></ul>实现 <code>NumMatrix</code> 类：<ul><li><code>NumMatrix(int[][] matrix)</code> 给定整数矩阵 <code>matrix</code> 进行初始化</li><li><code>int sumRegion(int row1, int col1, int row2, int col2)</code> 返回 左上角 <code>(row1, col1)</code> 、右下角 <code>(row2, col2)</code> 所形容的子矩阵的元素 总和 。</li></ul>示例 1：<pre><code>输出: [“NumMatrix”,“sumRegion”,“sumRegion”,“sumRegion”][[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]输入: [null, 8, 11, 12]解释:NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)</code></pre>如果本题持续双for循环，开销很大，如果sumRegion应用频繁，则能够应用一个前缀和数组存储NumMatrix前i行前j列的和。<h3>外围</h3>Q：二维数组的前缀和如何构建呢？A：行列的length各+1，而后找法则：右面的+下面的+本人-左对角线的Q：法则怎么找的？A：比方上图中的matrix(2)(2)，它值为0；当初要计算前3行前3列的前缀和。留神它右边的2和下面的3，如果让他俩各自地位的前缀和相加，而后再减去对角线的6地位的前缀和，就是0地位的前缀和。如下图所示（能够好好每每）： 代码如下：<pre><code class=“java”>class NumMatrix { public int[][] getPreMatrix() { return preMatrix; } private int[][] preMatrix; public NumMatrix(int[][] matrix) { preMatrix=new int[matrix.length+1][matrix[0].length+1]; //构建二维前缀和数组 for(int i=1;i< preMatrix.length;i++){ for (int j = 1; j < preMatrix[0].length; j++) { //找法则 //右面的+下面的+本人-左对角线的 preMatrix[i][j]=preMatrix[i][j-1]+preMatrix[i-1][j]+matrix[i-1][j-1]-preMatrix[i-1][j-1]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { return preMatrix[row2+1][col2+1] - preMatrix[row1][col2+1] - preMatrix[row2+1][col1] + preMatrix[row1][col1]; } public static void main(String[] args) { int[][] matrix = { {3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5} }; NumMatrix numMatrix = new NumMatrix(matrix); System.out.println(Arrays.deepToString(numMatrix.getPreMatrix())); System.out.println(numMatrix.sumRegion(2, 1, 4, 3)); }}</code></pre></article>