您的位置:365bet体育备用网址器 > 应用 > 题目描述 Given a 2D matrix matrix

题目描述 Given a 2D matrix matrix

2019-11-28 15:05

leetcode笔记:Range Sum Query 2D - Immutable

一. 题目描述

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

365bet在线官网 1

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.< 喎?" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+tv4uIMzixL+31s72PC9zdHJvbmc+PC9wPg0KPHA+zOLEv7Tz0uLKx6OsuPi2qNK7uPa2/s6svtjV86OsvMbL47TTz8Kx6jxjb2RlPihyb3cxLCBjb2wxKTwvY29kZT4gtb3PwrHqo7ogPGNvZGU+KHJvdzIsIGNvbDIpPC9jb2RlPrXE19O+2NXztcS6zaGjzOLEv7j4s/bBy7y4uPay4srU08PA/aGjPC9wPg0KPHA+16LS4srCz+7W0Mzhtb2jujwvcD4NCrzZyei+2NXzsru74bjEseSjuyBzdW1SZWdpb26jqLLp0a+jqbqvyv274bX308O63LbgtM6juyC82cnoPGNvZGU+cm93MSAmbGU7IHJvdzI8L2NvZGU+o6wgsqLH0iA8Y29kZT5jb2wxICZsZTsgY29sMjwvY29kZT6how0KPHA+uMPM4rXE1ti148rHyrm1sbbgtM6199PDc3VtUmVnaW9uuq/K/cqxo6zL47eoxNyxo7PWuN/Qp6Os0vK0y9fu1rG527XEt723qMrHyrnTw7/VvOS7u8ihyrG85KOszai5/bm51Oy4qNb6yv3X6Txjb2RlPnN1bVJlY29yZDwvY29kZT6jrDxjb2RlPnN1bVJlY29yZFtpXVtqXTwvY29kZT6x7cq+tNPPwrHqPGNvZGU+KDAsIDApPC9jb2RlPrW9PGNvZGU+KHgsIHkpPC9jb2RlPrXE19O+2NXztcS6zaOov7zCx7W9sd+9587KzOKjrLio1vrK/dfpPGNvZGU+c3VtUmVjb3JkPC9jb2RlPrTz0KHJ6M6qPGNvZGU+KG0gKyAxKSAqIChuICsgMSk8L2NvZGU+o6zG5NbQPGNvZGU+bTwvY29kZT66zTxjb2RlPm48L2NvZGU+t9ax8M6qyv3X6Txjb2RlPm1hdHJpeDwvY29kZT61xNDQyv26zcHQyv2jqaOsyrm1w8zixL/XqruvzqrH88ihvtjQzrHfvee1xM7KzOKjrMjnz8LD5sv5yr6hozwvcD4NCjxwPsO709DK1ravu63NvKOs0v3Tw834yc+1xM+1wdDNvMasvfjQ0L3iys2jujwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> +-----+-+-------+ +--------+-----+ +-----+---------+ +-----+--------+ | | | | | | | | | | | | | | | | | | | | | | | | | | +-----+-+ | +--------+ | | | | +-----+ | | | | | = | | + | | | - | | +-----+-+ | | | +-----+ | | | | | | | | | | | | | | | | | | | +---------------+ +--------------+ +---------------+ +--------------+ sumRecord[i][j] = sumRecord[i-1][j] + sumRecord[i][j-1] - sumRecord[i-1][j-1] + matrix[i-1][j-1]

这是小学学过的简单的矩形求面积方法,对于本题正好适用。

三. 示例代码

class NumMatrix {
public:
    NumMatrix(vector> &matrix) {
        int m = matrix.size();
        int n = m > 0 ? matrix[0].size() : 0;
        sumRecord = vector>(m + 1, vector(n + 1, 0));
        // 由于sumRegion函数可能被调用多次,因此使用辅助数组sumRecord用于
        // 记录matrix中坐标(0,0)到任一下标(i,j)之间矩形框内元素的值,这样
        // 每次调用sumRegion函数时只需查询sumRecord里的值并进行简单运算即可
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                sumRecord[i][j] = matrix[i - 1][j - 1] + sumRecord[i - 1][j] + sumRecord[i][j - 1] - sumRecord[i - 1][j - 1];
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sumRecord[row2 + 1][col2 + 1] - sumRecord[row1][col2 + 1] - sumRecord[row2 + 1][col1] + sumRecord[row1][col1];
    }

private:
    vector> sumRecord;
};


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

四. 小结

在构造辅助数组时,应考虑边界问题和下标的转换,否则容易出现越界等错误。

Sum Query 2D - Immutable 一. 题目描述 Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1...

304 - Range Sum Query 2D - Immutable

Total Accepted: 14771 Total Submissions: 66244 Difficulty: Medium

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given 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]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that 365bet在线官网,row1 ≤ row2 and col1 ≤ col2.

Hide Tags Dynamic Programming
Hide Similar Problems (E) Range Sum Query - Immutable (H) Range Sum Query 2D - Mutable

public class NumMatrix {

 private int[][] dp;

 public NumMatrix(int[][] matrix) {
  // https://leetcode.com/discuss/69047/clean-and-easy-to-understand-java-solution
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
   return;
  }
  int m = matrix.length;
  int n = matrix[0].length;
  dp = new int[m + 1][n + 1]; // dp[0][0] = 0, dp[0][j] = 0, dp[i][0] = 0,
         // 第一行第一列初始值为0

  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] + matrix[i - 1][j - 1];
   }
  }

 }

 public int sumRegion(int row1, int col1, int row2, int col2) {
  return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  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 } };

  // Your NumMatrix object will be instantiated and called as such:
  NumMatrix numMatrix = new NumMatrix(matrix);
  int sum1 = numMatrix.sumRegion(1, 2, 2, 4); // 12
  int sum2 = numMatrix.sumRegion(2, 1, 4, 3); // 8
  int sum3 = numMatrix.sumRegion(0, 1, 2, 3); // 19
  System.out.printf("sum1 = %d, sum2 = %d, sum3 = %d", sum1, sum2, sum3);

 }

}

本文由365bet体育备用网址器发布于应用,转载请注明出处:题目描述 Given a 2D matrix matrix

关键词: