304.二维区域和检索-矩阵不可变.md

304.二维区域和检索-矩阵不可变

/*
 * @lc app=leetcode.cn id=304 lang=typescript
 *
 * [304] 二维区域和检索 - 矩阵不可变
 */

// @lc code=start
class NumMatrix {
  constructor(matrix: number[][]) {}

  sumRegion(row1: number, col1: number, row2: number, col2: number): number {}
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */
// @lc code=end

解法 1: 动态规划

class NumMatrix {
  _prefixSums: number[][]

  constructor(matrix: number[][]) {
    this._prefixSums = this.generatePrefixSum(matrix)
  }

  generatePrefixSum(matrix: number[][]) {
    const [m, n] = [matrix.length, matrix[0].length]
    const dp: number[][] = new Array(m).fill(0).map(() => [])
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        dp[i][j] = (dp[i - 1]?.[j] ?? 0) + (dp[i][j - 1] ?? 0) - (dp[i - 1]?.[j - 1] ?? 0) + matrix[i][j]
      }
    }
    return dp
  }

  getPrefixSum = (row: number, col: number) => {
    return this._prefixSums[row]?.[col] ?? 0
  }

  sumRegion(r1: number, c1: number, r2: number, c2: number): number {
    const { getPrefixSum: get } = this
    return get(r2, c2) - get(r1 - 1, c2) - get(r2, c1 - 1) + get(r1 - 1, c1 - 1)
  }
}

Case

test.each([
  {
    input: {
      operations: ['NumMatrix', 'sumRegion', 'sumRegion', 'sumRegion'],
      params: [
        [
          [
            [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],
      ],
    },
    output: [null, 8, 11, 12],
  },
])(`input: n = $input.n`, ({ input: { operations, params }, output }) => {
  let numMatrix: NumMatrix = new NumMatrix((params as number[][][][])[0][0])
  const res: any[] = [null]
  for (let i = 1; i < operations.length; i++) {
    const operation: 'sumRegion' = operations[i] as any
    res.push(numMatrix[operation](...(params as [number, number, number, number][])[i]) ?? null)
  }

  expect(res).toEqual(output)
})