leetcode
leetcode 251 ~ 300
二维区域和检索 - 可变

二维区域和检索 - 可变

难度:

标签:

题目描述

代码结果

运行时间: 55 ms, 内存: 19.8 MB

/**
 * LeetCode 308: Range Sum Query 2D - Mutable
 *
 * 题目思路:
 * 1. 本题的复杂度较高，Java Stream 在处理更新和查询时不是最佳选择。
 * 2. 为了利用 Java Stream 进行处理，我们将主要使用集合和流的操作来简化代码。
 */
import java.util.*;
import java.util.stream.*;
 
public class NumMatrixStream {
    private int[][] matrix;
    private Map<Integer, Integer> bit;
    private int m, n;
 
    public NumMatrixStream(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        this.matrix = new int[matrix.length][matrix[0].length];
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.bit = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }
 
    public void update(int row, int col, int val) {
        int delta = val - matrix[row][col];
        matrix[row][col] = val;
        IntStream.iterate(col + 1, j -> j <= n, j -> j + (j & -j))
                  .forEach(j -> bit.merge(row * n + j, delta, Integer::sum));
    }
 
    private int prefixSum(int row, int col) {
        return IntStream.iterate(col, j -> j > 0, j -> j - (j & -j))
                        .map(j -> bit.getOrDefault(row * n + j, 0))
                        .sum();
    }
 
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return IntStream.rangeClosed(row1, row2)
                        .map(i -> prefixSum(i, col2 + 1) - prefixSum(i, col1))
                        .sum();
    }
}

解释

方法:

该题解使用了前缀和技巧。在构造函数中，通过对每一行计算前缀和，并将结果存储在二维数组 P 中。当需要更新某个元素时，只需要更新对应行的前缀和数组即可。在计算区域和时，可以利用前缀和的性质，对于每一行，用区域右端点的前缀和减去左端点的前缀和，然后将所有行的结果累加起来，即可得到最终的区域和。

时间复杂度:

构造函数: O(mn), update: O(n), sumRegion: O(m)

空间复杂度:

O(mn)

代码细节讲解

🦆
在构造函数中创建前缀和数组时，你是如何处理边界情况，比如矩阵为空或只有一行/一列的情况？
▷
在构造函数中，我们首先检查矩阵是否为空，如果为空，则前缀和数组也应该被初始化为空数组。对于只有一行或一列的情况，前缀和的计算方法仍然适用。即使矩阵仅有一个元素，我们同样计算其前缀和，这会是一个由一个元素加上一个初始的0组成的列表。总之，我们的前缀和数组的计算对于任何形状的矩阵都是通用的。
🦆
你的算法在执行 update 操作时是否考虑了可能对同一位置进行多次更新，这是否会影响累计的前缀和结果？
▷
在执行 update 操作时，我们首先在原始矩阵中更新指定位置的元素值。随后，为了确保前缀和数组的正确性，我们会重新计算整个行的前缀和。这种方法确保了即使同一位置进行多次更新，前缀和数组也总是与当前的矩阵状态保持一致，因此不会累积错误的结果。
🦆
在 sumRegion 函数中，你是如何确保计算的区域索引不会超出矩阵的有效边界？
▷
在 sumRegion 函数中，理论上应该有一步检查来确保输入的索引（row1, col1, row2, col2）都在矩阵的有效边界内。然而，在题解中并未明确这种检查。在实际应用中，应该添加适当的边界检查，如果输入的索引超出矩阵范围，应返回错误或进行适当的处理，以避免运行时错误。
🦆
当执行 update 操作后，你只更新了该行的前缀和，这种方法是否考虑了列之间的依赖关系？
▷
在本题解的前缀和数组设计中，每行的前缀和是独立计算的，不依赖于其他行的数据。因此，更新某个元素时，只需重新计算该元素所在行的前缀和，而不需要考虑列之间的依赖关系。这简化了更新操作，但仍能准确计算任何区域的和，因为区域和的计算是通过逐行计算并累加得到的。

相关问题

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

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

 

示例 1：

输入: 
["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 (蓝色矩形框的元素总和)

 

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -105 <= matrix[i][j] <= 105
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • 最多调用 104 次 sumRegion 方法

区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询。

  1. 其中一类查询要求 更新 数组 nums 下标对应的值
  2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

实现 NumArray 类：

  • NumArray(int[] nums) 用整数数组 nums 初始化对象
  • void update(int index, int val) 将 nums[index] 的值 更新 为 val
  • int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）

 

示例 1：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

 

提示：

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • 调用 update 和 sumRange 方法次数不大于 3 * 104 
区域和检索 - 数组可修改买卖股票的最佳时机含冷冻期