建设团购网站,企业宣传片制作教程,电子商务系统的组成,西安网站建设网站建设说在前面 #x1f388;不知道大家对于算法的学习是一个怎样的心态呢#xff1f;为了面试还是因为兴趣#xff1f;不管是出于什么原因#xff0c;算法学习需要持续保持。 问题描述
给你一个整数 n 和一个下标从 0 开始的 二维数组 queries #xff0c;其中 queries[i] [t…说在前面 不知道大家对于算法的学习是一个怎样的心态呢为了面试还是因为兴趣不管是出于什么原因算法学习需要持续保持。 问题描述
给你一个整数 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^41 queries.length 5 * 10^4queries[i].length 30 typei 10 indexi n0 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现在是一名前端工程师有空会刷刷算法题平时喜欢打羽毛球 平时也喜欢写些东西既为自己记录 也希望可以对大家有那么一丢丢的帮助写的不好望多多谅解 写错的地方望指出定会认真改进 偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章有兴趣的也可以关注下。在此谢谢大家的支持我们下文再见 。
