[数据结构与算法]Leetcode每日一题 1001. 网格照明

问题描述

原题链接：1001.网格照明

思路分析及代码实现

使用四个哈希表来分别表示行、列、正对角线、反对角线上的灯的数量

• 假设某灯的坐标为(xi,yi)，那么它所在的行的数值为xi，所在的列的数值为yi，正对角线的数值为xi-yi，反对角线的数值为xi+yi
• 遍历lamps，将遍历到的灯所在的四条线各加一 （注意去重，需要将重复的灯看作一盏灯）
• 遍历queries，判断当前查询点所在的四条线是否有灯，如果有，将该次查询值置1，然后进行关闭操作，查询当前点所在的八个相邻位置及其本身是否有灯， 如果有，将该点所在的四条线上的灯的数目减一，并且将该灯去除

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        points = set()
        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()
        for r, c in lamps:
            if (r, c) in points:
                continue
            points.add((r, c))
            row[r] += 1
            col[c] += 1
            diagonal[r - c] += 1
            antiDiagonal[r + c] += 1

        ans = [0] * len(queries)
        for i, (r, c) in enumerate(queries):
            if row[r] or col[c] or diagonal[r - c] or antiDiagonal[r + c]:
                ans[i] = 1
            for x in range(r - 1, r + 2):
                for y in range(c - 1, c + 2):
                    if x < 0 or y < 0 or x >= n or y >= n or (x, y) not in points:
                        continue
                    points.remove((x, y))
                    row[x] -= 1
                    col[y] -= 1
                    diagonal[x - y] -= 1
                    antiDiagonal[x + y] -= 1
        return ans