2718. 查询后矩阵的和

题目描述:

给你一个整数 n 和一个下标从 0 开始的 二维数组 queries ,其中 queries[i] = [typei, indexi, vali] 。

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

如果 typei == 0 ,将第 indexi 行的元素全部修改为 vali ,覆盖任何之前的值。
如果 typei == 1 ,将第 indexi 列的元素全部修改为 vali ,覆盖任何之前的值。
请你执行完所有查询以后,返回矩阵中所有整数的和。

示例 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 。

解题思路

这道题很巧妙,所以我决定把它分享出来。

这道题正常来讲,读完题第一反应就是直接暴力就能做,就改数呗,然后加和呗。

但是这有点太暴力了,那就优化一下,不改所有的数了,就改每一行的和和每一列的和呗,最后再统计一下总和。但这样似乎好像也不是很好实现。因为我们把每一行和每一列的和记录下来之后,最后算总和的时候是不太好计算的,因为后改变的会覆盖先改变的,所以我们还得知道行和列改变的顺序关系才行。

那考虑到这,注意到加粗的“顺序关系”了么,没错,这就是解题关键。

后改变的会覆盖先改变的,也就是说,我只需要从最后改变的开始往前遍历就行了,最后改变的一定是贡献给最终答案的,那先前改变的就没有作用了。所以无论是行还是列,我们都只关注他是不是最后改变的,我们从后往前遍历的话,也就是关注他是不是第一个出现的,如果是那就更新最终的答案的值,如果不是说明在这个操作后面有另一个操作把它覆盖了,这个操作不起作用。

代码

class Solution {
public:
    long long matrixSumQueries(int n, vector<vector<int>>& queries) {
        long long int ans = 0;
        unordered_set<int> vis[2]; //0表示行是否被修改,1表示列是否被修改
        int m = queries.size();
        for(int i = m - 1 ; i >= 0 ; i--){
            auto &q = queries[i];
            int type = q[0] , index = q[1] , val = q[2];
            if(!vis[type].count(index)){//如果该行/列没有被修改过
                ans += (long long int)(n-vis[type^1].size())*val;//更新答案,该行/列首次发生改变的数要加到最终答案里
                vis[type].insert(index);//标记该行/列已经被修改过
            }
        }
        return ans;
    }
};

上一篇:React的JSX语法学习和常见的插值{}内容情况-1.React JSX概念


下一篇:关系型数据库和非关系型数据库