[Leetcode] 2718. Sum of Matrix After Queries (Medium)

概述

題目

https://leetcode.com/problems/sum-of-matrix-after-queries/
給定一個 n* n 的 grid，每次 queries 會將其中的 row (0) 或 col (1) 的第 k row or col 全改寫成 val，求最終所有 grid 中數值總和為何

心得

因為前改會被後蓋，所以反向思考，queries 從後往前

Set

思路

計算還有多少未被覆蓋的數值，加總即可

程式

class Solution(object):
    def matrixSumQueries(self, n, queries):
        """
        :type n: int
        :type queries: List[List[int]]
        :rtype: int
        """
        r, c = set(), set()
        for i in range(n):
            r.add(i)
            c.add(i)

        cnt = 0
        for t, k, v in queries[::-1]:
            if t == 0:
                if k in r:
                    cnt += v*len(c)
                    r.remove(k)
            else:
                if k in c:
                    cnt += v*len(r)
                    c.remove(k)
        return cnt

Complexity

Time Complexity: O(n)
走過多少 queries 數值

Space Complexity: O(n)
rol, col 都用 set 去存

Hash

思路

from vicML，透過 Hash 記錄還沒有走過的 row 或 col，並將餘下數字補走

程式

class Solution(object):
    def matrixSumQueries(self, n, queries):
        """
        :type n: int
        :type queries: List[List[int]]
        :rtype: int
        """
        vis = set()
        q = len(queries)
        # 分別代表最初 row, col 各有 n 個數字
        mis = [n, n]
        cnt = 0

        for t, i, v in queries[::-1]:
            if (t, i) not in vis:
                vis.add((t, i))
                cnt += v * mis[t]
                # 每次 -1
                mis[t^1] -= 1
        return cnt