问题描述 链接到标题

2718. 查询后矩阵的和 (Medium) 给你一个整数 n 和一个下标从 0 开始的 二维数组 que ries ,其中 queries[i] = [typeᵢ, indexᵢ, valᵢ]

一开始,给你一个下标从 0 开始的 n x n 矩阵,所有元素均 为 0 。每一个查询,你需要执行以下操作之一:

  • 如果 typeᵢ == 0 ,将第 indexᵢ 行的元素全部修改为 valᵢ ,覆盖任何之前的值。
  • 如果 typeᵢ == 1 ,将第 indexᵢ 列的元素全部修改为 valᵢ ,覆盖任何之前的值。

请你执行完所有查询以后,返回矩阵中所有整数的和。

示例 1:

输入:n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
输出:23
解释:上图展示了每个查询以后矩阵的值。所有操作执行完以后,矩
阵元素之和为 23 。

示例 2:

输入:n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2
,1]]
输出:17
解释:上图展示了每一个查询操作之后的矩阵。所有操作执行完以后
,矩阵元素之和为 17 。

提示:

  • 1 <= n <= 10⁴
  • 1 <= queries.length <= 5 * 10⁴
  • queries[i].length == 3
  • 0 <= typeᵢ <= 1
  • 0 <= indexᵢ < n
  • 0 <= valᵢ <= 10⁵

解题思路 链接到标题

本题是 Leetcode 第 348 期的第三题,当时太蠢了,做了半天搞不定,一直在想是不是要用什么高级的数据结构,实际上并不难,主要是脑子要转过这个弯。

本题本质上还是个模拟题,只是如果按照题目意思,正序模拟,一步步修改数值并调整覆盖,那么就掉坑里了,必然超时。

正难则反,实际上,我们可以尝试倒序进行模拟,那么我们就不用考虑覆盖了,只需考虑行填充或者列填充时,填充多少个。

我们可以用哈希表来记录未被填充的行或者列,倒序遍历时,如果发现当前行已经被填充了,那就跳过,否则给 $total$ 加上 $val \times k$,$k$ 表示还没有被填充的列的数目;填充列的情况是类似的。

代码 链接到标题

class Solution {
  public:
    long long matrixSumQueries(int n, vector<vector<int>> &queries) {
        // 倒序处理
        unordered_set<int> col_hash, row_hash;
        for (int i = 0; i < n; ++i) {
            col_hash.insert(i);
            row_hash.insert(i);
        }
        int m = queries.size();
        long long total = 0;
        for (int i = m - 1; i >= 0 && !col_hash.empty() && !row_hash.empty(); --i) {
            if (queries[i][0] == 0) {
                // 修改行
                if (row_hash.find(queries[i][1]) == row_hash.end()) {
                    // 说明后面还会被修改,直接不管他
                    continue;
                }
                total += col_hash.size() * queries[i][2];
                row_hash.erase(queries[i][1]);
            } else {
                // 修改列
                if (col_hash.find(queries[i][1]) == col_hash.end()) {
                    continue;
                }
                total += row_hash.size() * queries[i][2];
                col_hash.erase(queries[i][1]);
            }
        }
        return total;
    }
};