Skip to content

Latest commit

 

History

History
250 lines (212 loc) · 10.1 KB

README.md

File metadata and controls

250 lines (212 loc) · 10.1 KB

1001. 网格照明

English Version

题目描述

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。

给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。

当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。

另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 。对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯。

返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。

 

示例 1：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[1,0]
解释：最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。第 0 次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。

第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。

示例 2：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
输出：[1,1]

示例 3：

输入：n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
输出：[1,1,0]

 

提示：

  • 1 <= n <= 109
  • 0 <= lamps.length <= 20000
  • 0 <= queries.length <= 20000
  • lamps[i].length == 2
  • 0 <= rowi, coli < n
  • queries[j].length == 2
  • 0 <= rowj, colj < n

解法

哈希表。

假设一盏灯的坐标为 (x, y)，那么它所在的行的数值为 x，列的数值为 y，正对角线的数值为 x-y，反对角线的数值为 x+y。确定某一直线的唯一数值标识后，我们就可以通过哈希表来记录某一直线所拥有的灯的数目。

遍历 lamps，将当前遍历到的灯所在的行、列和正、反对角线拥有灯的数目分别加 1。

在处理 lamps 时，需要进行去重，因为我们将重复的灯看作同一盏灯。

遍历 queries，判断当前查询点所在的行，列和正、反对角线是否有灯，如果有，则置 1，即该点在查询时是被照亮的。然后进行关闭操作，查找查询点所在的八近邻点及它本身是否有灯，如果有，将该点所在的行、列和正、反对角线的灯数目分别减 1，并且将灯从网格中去掉。

Python3

class Solution:
    def gridIllumination(
        self, n: int, lamps: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        points = set()
        rcnt, ccnt, dgcnt, udgcnt = Counter(), Counter(), Counter(), Counter()
        for r, c in lamps:
            if (r, c) not in points:
                points.add((r, c))
                rcnt[r] += 1
                ccnt[c] += 1
                dgcnt[r - c] += 1
                udgcnt[r + c] += 1
        ans = [0] * len(queries)
        for i, q in enumerate(queries):
            r, c = q
            if rcnt[r] or ccnt[c] or dgcnt[r - c] or udgcnt[r + c]:
                ans[i] = 1
                for a, b in [
                    (0, 1),
                    (1, 0),
                    (0, -1),
                    (-1, 0),
                    (0, 0),
                    (1, 1),
                    (-1, 1),
                    (1, -1),
                    (-1, -1),
                ]:
                    x, y = r + a, c + b
                    if (x, y) in points:
                        points.remove((x, y))
                        rcnt[x] -= 1
                        ccnt[y] -= 1
                        dgcnt[x - y] -= 1
                        udgcnt[x + y] -= 1
        return ans

Java

class Solution {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Set<Long> points = new HashSet<>();
        Map<Integer, Integer> rcnt = new HashMap<>();
        Map<Integer, Integer> ccnt = new HashMap<>();
        Map<Integer, Integer> dgcnt = new HashMap<>();
        Map<Integer, Integer> udgcnt = new HashMap<>();
        for (int[] l : lamps) {
            int r = l[0], c = l[1];
            long v = r * n + c;
            if (!points.contains(v)) {
                points.add(v);
                rcnt.put(r, rcnt.getOrDefault(r, 0) + 1);
                ccnt.put(c, ccnt.getOrDefault(c, 0) + 1);
                dgcnt.put(r - c, dgcnt.getOrDefault(r - c, 0) + 1);
                udgcnt.put(r + c, udgcnt.getOrDefault(r + c, 0) + 1);
            }
        }
        int[][] dirs
            = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {0, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int r = queries[i][0], c = queries[i][1];
            if (rcnt.getOrDefault(r, 0) > 0 || ccnt.getOrDefault(c, 0) > 0
                || dgcnt.getOrDefault(r - c, 0) > 0 || udgcnt.getOrDefault(r + c, 0) > 0) {
                ans[i] = 1;
                for (int[] d : dirs) {
                    int x = r + d[0], y = c + d[1];
                    long v = x * n + y;
                    if (x < 0 || x >= n || y < 0 || y >= n || !points.contains(v)) {
                        continue;
                    }
                    points.remove(v);
                    rcnt.put(x, rcnt.get(x) - 1);
                    if (rcnt.get(x) == 0) {
                        rcnt.remove(x);
                    }
                    ccnt.put(y, ccnt.get(y) - 1);
                    if (ccnt.get(y) == 0) {
                        ccnt.remove(y);
                    }
                    dgcnt.put(x - y, dgcnt.get(x - y) - 1);
                    if (dgcnt.get(x - y) == 0) {
                        dgcnt.remove(x - y);
                    }
                    udgcnt.put(x + y, udgcnt.get(x + y) - 1);
                    if (udgcnt.get(x + y) == 0) {
                        udgcnt.remove(x + y);
                    }
                }
            }
        }
        return ans;
    }
}

TypeScript

function gridIllumination(
    n: number,
    lamps: number[][],
    queries: number[][],
): number[] {
    let lights: Set<string> = new Set();
    let rows: Map<number, number> = new Map(); // i
    let cols: Map<number, number> = new Map(); // j
    let mainDiagonal: Map<number, number> = new Map(); // i - j
    let subDiagonal: Map<number, number> = new Map(); // i + j
    for (let [i, j] of lamps) {
        let key = `${i},${j}`;
        if (lights.has(key)) continue;
        lights.add(key);
        rows.set(i, (rows.get(i) || 0) + 1);
        cols.set(j, (cols.get(j) || 0) + 1);
        mainDiagonal.set(i - j, (mainDiagonal.get(i - j) || 0) + 1);
        subDiagonal.set(i + j, (subDiagonal.get(i + j) || 0) + 1);
    }

    let ans: Array<number> = [];
    let directions = [
        [-1, -1],
        [-1, 0],
        [-1, 1],
        [0, -1],
        [0, 0],
        [0, 1],
        [1, -1],
        [1, 0],
        [1, 1],
    ];
    for (let [i, j] of queries) {
        // check
        const check =
            lights.has(`${i},${j}`) ||
            rows.get(i) ||
            cols.get(j) ||
            mainDiagonal.get(i - j) ||
            subDiagonal.get(i + j);
        ans.push(check ? 1 : 0);
        // close lamp
        for (let [dx, dy] of directions) {
            const [x, y] = [i + dx, j + dy];
            let key = `${x},${y}`;
            if (x < 0 || x > n - 1 || y < 0 || y > n - 1 || !lights.has(key)) {
                continue;
            }
            lights.delete(key);
            rows.set(x, rows.get(x) - 1);
            cols.set(y, cols.get(y) - 1);
            mainDiagonal.set(x - y, mainDiagonal.get(x - y) - 1);
            subDiagonal.set(x + y, subDiagonal.get(x + y) - 1);
        }
    }
    return ans;
}

...