Day 23 题目：二维区域和检索

leetcode链接：二维区域和检索
要点：前缀和

创新互联2013年至今，公司以成都网站设计、成都做网站、系统开发、网络推广、文化传媒、企业宣传、平面广告设计等为主要业务，适用行业近百种。服务企业客户上1000家，涉及国内多个省份客户。拥有多年网站建设开发经验。为企业提供专业的网站建设、创意设计、宣传推广等服务。 通过专业的设计、独特的风格，为不同客户提供各种风格的特色服务。1、Java

class NumMatrix {// 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
    private int[][] preSum;
    public NumMatrix(int[][] matrix) {int m = matrix.length;
        int n = matrix[0].length;
        if(m == 0 || n == 0) return;
        // 构造前缀和矩阵
        preSum = new int[m + 1][n + 1];
        for(int i = 1; i< m + 1; i++){for(int j = 1; j< n + 1; j++){// 计算每个矩阵 [0, 0, i, j] 的元素和
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i -1][j - 1];
            }
        }
    }
    
    // 计算子矩阵 [x1, y1, x2, y2] 的元素和
    public int sumRegion(int row1, int col1, int row2, int col2) {// 目标矩阵之和由四个相邻矩阵运算获得
        return preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1] - preSum[row1][col2 + 1] + preSum[row1][col1];
    }
}

2、python

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), (len(matrix[0]) if matrix else 0)
        self.sums = [[0] * (n + 1) for _ in range(m + 1)]
        _sums = self.sums

        for i in range(m):
            for j in range(n):
                _sums[i + 1][j + 1] = _sums[i][j + 1] + _sums[i + 1][j] - _sums[i][j] + matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) ->int:
        _sums = self.sums

        return _sums[row2 + 1][col2 + 1] - _sums[row1][col2 + 1] - _sums[row2 + 1][col1] + _sums[row1][col1]

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：Day23leetcode二维区域和检索-创新互联
网址分享：http://scyanting.com/article/dpcjec.html