查询后矩阵的和

🎈 算法并不一定都是很难的题目，也有很多只是一些代码技巧，多进行一些算法题目的练习，可以帮助我们开阔解题思路，提升我们的逻辑思维能力，也可以将一些算法思维结合到业务代码的编写思考中。简而言之，平时进行的算法习题练习带给我们的好处一定是不少的，所以让我们一起来养成算法练习的习惯。今天练习的题目是一道比较简单的题目 ->查询后矩阵的和

问题描述

给你一个整数 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 。

提示：

• 1 <= n <= 10^4
• 1 <= queries.length <= 5 * 10^4
• queries[i].length == 3
• 0 <= typei <= 1
• 0 <= indexi < n
• 0 <= vali <= 10^5

思路分析

首先我们应该要先理解一下题目意思，题目会给我们一个整数 n 和一个下标从 0 开始的 二维数组 queries ，n表示我们有一个下标从 0 开始的 n x n 矩阵，所有元素均为 0。queries表示有若干个查询，其中 queries[i] = [typei, indexi, vali]，每一个查询，我们需要执行以下操作之一：

• 如果 typei == 0 ，将第 indexi 行的元素全部修改为 vali ，覆盖任何之前的值。
• 如果 typei == 1 ，将第 indexi 列的元素全部修改为 vali ，覆盖任何之前的值。

我们要计算执行完所有查询以后，矩阵中所有整数的和。

这里有一个关键的点，就是每一个修改都会覆盖任何之前的值，也就是说有重复修改的话，生效的只会是最后修改的那一次。所以我们可以换个思路来想，如果我们将queries的顺序倒过来查询的话，那么生效的只会是第一次操作的那一次，这样的话我们可以再修改的时候判断一下当前行或列还有多少是没有被操作过的，填上没操作过的坑位即可。

• 1、使用两个set分别记录被操作过的行和列

因为我们是逆序来操作，所以生效的只会是第一次操作，我们需要记录被操作过的行和列.

const colSet = new Set(),rowSet = new Set();

• 2、修改行元素

如果 typei == 0 ，将第 indexi 行的元素全部修改为 vali ，覆盖任何之前的值，能增加的数值为当前行中未被修改过的元素 * vali.

if(type == 0){
    if(!colSet.has(index)){
        res += (n - rowSet.size) * val;
        colSet.add(index);
    }
}

• 3、修改列元素

如果 typei == 1 ，将第 indexi 列的元素全部修改为 vali ，覆盖任何之前的值，能增加的数值为当前列中未被修改过的元素 * vali。

if(type == 1){
    if(!rowSet.has(index)){
        res += (n - colSet.size) * val;
        rowSet.add(index);
    }
}

AC 代码

完整 AC 代码如下：

/**
 * @param {number} n
 * @param {number[][]} queries
 * @return {number}
 */
var matrixSumQueries = function(n, queries) {
    let res = 0;
    const colSet = new Set(),rowSet = new Set();
    for(let i = queries.length - 1; i >= 0; i--){
        const [type,index,val] = queries[i];
        if(type == 0){
            if(!colSet.has(index)){
                res += (n - rowSet.size) * val;
                colSet.add(index);
            }
        }else{
            if(!rowSet.has(index)){
                res += (n - colSet.size) * val;
                rowSet.add(index);
            }
        }
    }
    return res;
};

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，在此谢谢大家的支持，我们下文再见 🙌。