前缀和，二维前缀和，求数组的区间和、矩阵指定区域面积，并建立四叉树。求解《303. 区域和检索 - 数组不可变》《304. 二维区域和检索 - 矩阵不可变》《427. 建立四叉树》
前缀和
- 建立长度+1前缀和数组（向右后移一位）
- 区间求和：
right + 1对应和 -left对应和
二维前缀和
- 建立行数 + 1 和 列数 + 1的二维前缀和数组（向右下角后移一位）
- 矩阵求面积：从左上角到右下角，过程模拟如上图
- 矩阵左上角到当前点面积：
sums(row + 1, col + 1) = sums(row, col + 1) + sums(row + 1, col) – sums(row, row) + matrix(row, col) - 矩阵指定区域面积：
sum(row1, col2, row2, col2) = sums(row2, col2) – sums(row1, col2) – sums(row2, col1) + sums(row1, col1)
- 矩阵左上角到当前点面积：
例题
303. 区域和检索 - 数组不可变
给定一个整数数组 nums，处理以下类型的多个查询: 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right 实现 NumArray 类： NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )
答案
前缀和
var NumArray = function(nums) {
const n = nums.length
this.sums = new Int32Array(n + 1)
for (let i = 0; i < n; i++) {
this.sums[i + 1] = this.sums[i] + nums[i]
}
};
NumArray.prototype.sumRange = function(left, right) {
return this.sums[right + 1] - this.sums[left]
}; type NumArray struct {
sums []int
}
func Constructor(nums []int) NumArray {
sums := make([]int, len(nums) + 1)
for i, v := range nums {
sums[i + 1] = sums[i] + v
}
return NumArray{sums}
}
func (this *NumArray) SumRange(left int, right int) int {
return this.sums[right + 1] - this.sums[left]
}class NumArray {
protected $nums;
function __construct($nums) {
$n = count($nums);
$this->sums = Array($n + 1);
for ($i = 0; $i < $n; $i++) {
$this->sums[$i + 1] = $this->sums[$i] + $nums[$i];
}
}
function sumRange($left, $right) {
return $this->sums[$right + 1] - $this->sums[$left];
}
}304. 二维区域和检索 - 矩阵不可变
给定一个二维矩阵 matrix，以下类型的多个请求： 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。 实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
答案
二维前缀和
var NumMatrix = function(matrix) {
const m = matrix.length, n = matrix[0].length
const sums = Array.from({length: m + 1}, _ => new Int32Array(n + 1))
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j]
}
}
this.sums = sums
};
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
const sums = this.sums
return sums[row2 + 1][col2 + 1] - sums[row2 + 1][col1] - sums[row1][col2 + 1] + sums[row1][col1]
}; type NumMatrix struct {
sums [][]int
}
func Constructor(matrix [][]int) NumMatrix {
m, n := len(matrix), len(matrix[0])
sums := make([][]int, m + 1)
for i := 0; i <= m; i++ {
sums[i] = make([]int, n + 1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j]
}
}
return NumMatrix{sums}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
sums := this.sums
return sums[row2 + 1][col2 + 1] - sums[row2 + 1][col1] - sums[row1][col2 + 1] + sums[row1][col1]
}class NumMatrix {
function __construct($matrix) {
$m = count($matrix);
$n = count($matrix[0]);
$sums = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
for ($i = 0; $i < $m; $i++) {
for ($j = 0; $j < $n; $j++) {
$sums[$i + 1][$j + 1] = $sums[$i][$j + 1] + $sums[$i + 1][$j] - $sums[$i][$j] + $matrix[$i][$j];
}
}
$this->sums = $sums;
}
function sumRegion($row1, $col1, $row2, $col2) {
$sums = $this->sums;
return $sums[$row2 + 1][$col2 + 1] - $sums[$row2 + 1][$col1] - $sums[$row1][$col2 + 1] + $sums[$row1][$col1];
}
}427. 建立四叉树
给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
你需要返回能表示矩阵的 四叉树 的根结点。
注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：
val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False；
isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。class Node { public boolean val; public boolean isLeaf; public Node topLeft; public Node topRight; public Node bottomLeft; public Node bottomRight; }我们可以按以下步骤为二维区域构建四叉树：
如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。
如果你想了解更多关于四叉树的内容，可以参考 wiki 。
四叉树格式：
输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。
它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。
如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。
答案
递归
var construct = function(grid) {
const d = (row1, col1, row2, col2) => {
let isSame = true
for (let i = row1; i < row2; i++) {
for (let j = col1; j < col2; j++) {
if (grid[row1][col1] !== grid[i][j]) {
isSame = false
break
}
}
}
if (isSame === true) return new Node(grid[row1][col1] === 1, true)
const dx = row2 - row1 >> 1
const dy = col2 - col1 >> 1
return new Node(
true,
false,
d(row1, col1, row1 + dx, col1 + dy),
d(row1, col1 + dy, row1 + dx, col2),
d(row1 + dx, col1, row2, col1 + dy),
d(row1 + dx, col1 + dy, row2, col2),
)
}
return d(0, 0, grid.length, grid[0].length)
};func construct(grid [][]int) *Node {
var d func(row1 int, col1 int, row2 int, col2 int) *Node
d = func(row1 int, col1 int, row2 int, col2 int) *Node {
isSame := true
for i := row1; i < row2; i++ {
for j := col1; j < col2; j++ {
if grid[row1][col1] != grid[i][j] {
isSame = false
break
}
}
}
if isSame {
return &Node{Val: grid[row1][col1] == 1, IsLeaf: true}
}
dx := (row2 - row1) >> 1
dy := (col2 - col1) >> 1
return &Node{
Val: true,
IsLeaf: false,
TopLeft: d(row1, col1, row1 + dx, col1 + dy),
TopRight: d(row1, col1 + dy, row1 + dx, col2),
BottomLeft: d(row1 + dx, col1, row2, col1 + dy),
BottomRight: d(row1 + dx, col1 + dy, row2, col2),
}
}
return d(0, 0, len(grid), len(grid[0]))
}class Solution {
protected $grid;
function construct($grid) {
$this->grid = $grid;
return $this->d(0, 0, count($grid), count($grid[0]));
}
function d($row1, $col1, $row2, $col2) {
$grid = $this->grid;
$isSame = true;
for ($i = $row1; $i < $row2; $i++) {
for ($j = $col1; $j < $col2; $j++) {
if ($grid[$row1][$col1] !== $grid[$i][$j]) {
$isSame = false;
break;
}
}
}
if ($isSame) return new Node($grid[$row1][$col1] === 1, true);
$dx = $row2 - $row1 >> 1;
$dy = $col2 - $col1 >> 1;
$node = new Node(true, false);
$node->topLeft = $this->d($row1, $col1, $row1 + $dx, $col1 + $dy);
$node->topRight = $this->d($row1, $col1 + $dy, $row1 + $dx, $col2);
$node->bottomLeft = $this->d($row1 + $dx, $col1, $row2, $col1 + $dy);
$node->bottomRight = $this->d($row1 + $dx, $col1 + $dy, $row2, $col2);
return $node;
}
}递归 · 二维前缀和
var construct = function(grid) {
const m = grid.length, n = grid[0].length, sums = Array.from({length: m + 1}, _ => new Uint32Array(n + 1))
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + grid[i][j]
}
}
const sum = (row1, col1, row2, col2) => {
return sums[row2][col2] - sums[row2][col1] - sums[row1][col2] + sums[row1][col1]
}
const d = (row1, col1, row2, col2) => {
const total = sum(row1, col1, row2, col2)
if (total === 0 || total === (col2 - col1) * (row2 - row1)) return new Node(total !== 0, true)
const dx = row2 - row1 >> 1, dy = col2 - col1 >> 1
return new Node(
true,
false,
d(row1, col1, row1 + dx, col1 + dy),
d(row1, col1 + dy, row1 + dx, col2),
d(row1 + dx, col1, row2, col1 + dy),
d(row1 + dx, col1 + dy, row2, col2)
)
}
return d(0, 0, m, n)
};func construct(grid [][]int) *Node {
m, n := len(grid), len(grid[0])
sums := make([][]int, m + 1)
for i := 0; i <= m; i++ {
sums[i] = make([]int, n + 1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + grid[i][j]
}
}
var sum func(row1 int, col1 int, row2 int, col2 int) int
sum = func(row1 int, col1 int, row2 int, col2 int) int {
return sums[row2][col2] - sums[row2][col1] - sums[row1][col2] + sums[row1][col1]
}
var d func(row1 int, col1 int, row2 int, col2 int) *Node
d = func(row1 int, col1 int, row2 int, col2 int) *Node {
total := sum(row1, col1, row2, col2)
if total == 0 || total == (row2 - row1) * (col2 - col1) {
return &Node{Val: total != 0, IsLeaf: true}
}
dx, dy := (row2 - row1) >> 1, (col2 - col1) >> 1
return &Node{
Val: true,
IsLeaf: false,
TopLeft: d(row1, col1, row1 + dx, col1 + dy),
TopRight: d(row1, col1 + dy, row1 + dx, col2),
BottomLeft: d(row1 + dx, col1, row2, col1 + dy),
BottomRight: d(row1 + dx, col1 + dy, row2, col2),
}
}
return d(0, 0, m, n)
}class Solution {
protected $sums;
function construct($grid) {
$m = count($grid);
$n = count($grid[0]);
$sums = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
for ($i = 0; $i < $m; $i++) {
for ($j = 0; $j < $n; $j++) {
$sums[$i + 1][$j + 1] = $sums[$i][$j + 1] + $sums[$i + 1][$j] - $sums[$i][$j] + $grid[$i][$j];
}
}
$this->sums = $sums;
return $this->d(0, 0, $m, $n);
}
function sum($row1, $col1, $row2, $col2) {
$sums = $this->sums;
return $sums[$row2][$col2] - $sums[$row2][$col1] - $sums[$row1][$col2] + $sums[$row1][$col1];
}
function d($row1, $col1, $row2, $col2) {
$total = $this->sum($row1, $col1, $row2, $col2);
if ($total === 0 || $total === ($row2 - $row1) * ($col2 - $col1)) return new Node($total !== 0, true);
$dx = $row2 - $row1 >> 1;
$dy = $col2 - $col1 >> 1;
$node = new Node(true, false);
$node->topLeft = $this->d($row1, $col1, $row1 + $dx, $col1 + $dy);
$node->topRight = $this->d($row1, $col1 + $dy, $row1 + $dx, $col2);
$node->bottomLeft = $this->d($row1 + $dx, $col1, $row2, $col1 + $dy);
$node->bottomRight = $this->d($row1 + $dx, $col1 + $dy, $row2, $col2);
return $node;
}
}
