列表

详情

6472. 查询后矩阵的和

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

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

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

 

示例 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) { } };

python3 解法, 执行用时: 160 ms, 内存消耗: 34.5 MB, 提交时间: 2023-06-05 09:44:09 

class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
        row = set()
        col = set()
        
        res = 0
        for t,idx,val in queries[::-1]:
            # 行
            if t == 0 and (idx not in row):
                # 受列限制
                res += val*(n-len(col))
                row.add(idx)
            # 列    
            if t == 1 and (idx not in col):
                # 受行限制
                res += val*(n-len(row))
                col.add(idx)
        
        return res

cpp 解法, 执行用时: 544 ms, 内存消耗: 207 MB, 提交时间: 2023-06-05 09:43:35 

class Solution {
public:
    long long matrixSumQueries(int n, vector<vector<int>> &queries) {
        long long ans = 0;
        unordered_set<int> vis[2];
        for (int i = queries.size() - 1; i >= 0; i--) {
            auto &q = queries[i];
            int type = q[0], index = q[1], val = q[2];
            if (!vis[type].count(index)) { // 后面（>i）没有对这一行/列的操作
                // 这一行/列还剩下 n-vis[type^1].size() 个可以填入的格子
                ans += (long long) (n - vis[type ^ 1].size()) * val;
                vis[type].insert(index);
            }
        }
        return ans;
    }
};

golang 解法, 执行用时: 324 ms, 内存消耗: 11.7 MB, 提交时间: 2023-06-05 09:43:17 

func matrixSumQueries(n int, queries [][]int) (ans int64) {
	vis := [2]map[int]bool{{}, {}}
	for i := len(queries) - 1; i >= 0; i-- {
		q := queries[i]
		tp, index, val := q[0], q[1], q[2]
		if !vis[tp][index] { // 后面（>i）没有对这一行/列的操作
			// 这一行/列还剩下 n-len(vis[tp^1]) 个可以填入的格子
			ans += int64(n-len(vis[tp^1])) * int64(val)
			vis[tp][index] = true // 标记操作过
		}
	}
	return
}

java 解法, 执行用时: 17 ms, 内存消耗: 60.8 MB, 提交时间: 2023-06-05 09:43:05 

class Solution {
    public long matrixSumQueries(int n, int[][] queries) {
        long ans = 0;
        Set<Integer>[] vis = new Set[]{new HashSet<>(), new HashSet<>()};
        for (int i = queries.length - 1; i >= 0; i--) {
            var q = queries[i];
            int type = q[0], index = q[1], val = q[2];
            if (!vis[type].contains(index)) { // 后面（>i）没有对这一行/列的操作
                // 这一行/列还剩下 n-vis[type^1].size() 个可以填入的格子
                ans += (long) (n - vis[type ^ 1].size()) * val;
                vis[type].add(index);
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 180 ms, 内存消耗: 35.1 MB, 提交时间: 2023-06-05 09:42:36 

'''
倒序操作

如果对同一行反复操作，那么只有最后一次对这行的操作会计入答案。列同理。
倒序操作queries
'''
class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
        ans = 0
        vis = [set(), set()]
        for type, index, val in reversed(queries):
            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作
                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子
                ans += (n - len(vis[type ^ 1])) * val
                vis[type].add(index)  # 标记操作过
        return ans

上一题

© 2024 leetcode.cn