查询后矩阵的和

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

问题描述

给你一个整数?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，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。