每日一题:LeetCode:1001.网格照明

浏览次数 : 次 2022-02-08

博文字数统计 : 1.4k字 | 阅读所需时长 : 5分

× 文章目录

1. 2022-02-08：LeetCode：1001.网格照明
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法一：哈希表

每日一题：LeetCode：1001.网格照明
- 时间：2022-02-08
- 力扣难度：Hard
- 个人难度：Hard-
- 数据结构：数组、哈希表
- 算法：贪心、排序

2022-02-08：LeetCode：1001.网格照明

1. 题目描述

题目：原题链接
- 在大小为 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 个方向上（与该单元格共享角或边）的任何灯。
- 返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。
- 1 <= n <= 10^9
- 0 <= lamps.length <= 20000
- 0 <= queries.length <= 20000
- lamps[i].length == 2
- 0 <= rowi, coli < n
- queries[j].length == 2
- 0 <= rowj, colj < n
输入输出规范
- 输入：网格大小n，打开的灯泡的坐标lamps，查询的坐标queries
- 输出：查询的结果
输入输出示例
- 输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
- 输出：[1,1]

2. 方法一：哈希表

思路
- 本题主要分为两个阶段，一个是打开灯并点亮周围的过程，另一个是查询过程中每次会关闭灯
- 最简单的方法是，维护一个二维数组表示网格每个位置的亮暗，遍历lamps和queries数组来直接模拟这个开灯照亮和查询关灯的过程，更新网格的亮暗
- 但是，由于本题的网格维度 n 是 $10^9$，模拟整个二维数组一定会TLE超时，不过lamps和queries数组的维度只有20000，应该从这里入手
- 为了得到查询的网格位置的亮暗，我们可以通过哈希表来储存开灯后照亮的所有位置，并在查询时将灭了的位置从哈希表中去除
- 但是由于点亮一个灯会照亮所在行、列及两个对角线，即要保存 4n 个坐标，同样维度太大，所以应该换一种思路来保存照亮的位置：坐标线段映射
- 具体而言，行和列对应的位置可以直接通过打开的灯的横纵坐标(x, y)来唯一表示
- 对于两条对角线对应的位置，可以发现其横纵坐标分别满足 x - y 和 x + y，即通过线段的截距表示
- 这样在遍历lamps数组时，就只需要对每一个元素保存对应的四个方向(行、列、左右对角线)线段的标识即可，key为线段标识，value为照亮的次数，维度是 $4*20000$
- 同时，由于行、列、对角线的标识可能冲突，比如$x1 = x2 + y2$，所以要分别使用四个哈希表来分别存储，表示四个照亮线段的哈希表
- 另一方面，因为查询时会关灯，所以需要一个哈希表来存储灯的坐标，可以存为String类型或数值类型
- 并且在遍历queries数组查询的时候，将关闭的灯从该哈希表中去除，同时去更新四个照亮线段的哈希表
- 查询的过程中，判断四个照亮线段的哈希表中是否存在当前查询的坐标，来判断亮暗

题解

public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
    int[][] dirs = new int[][]{{0, 0}, {0, 1}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {1, 0}, {1, 1}};
    Map<Integer, Integer> rowMap = new HashMap<>();
    Map<Integer, Integer> colMap = new HashMap<>();
    Map<Integer, Integer> leftMap = new HashMap<>();
    Map<Integer, Integer> rightMap = new HashMap<>();
    Set<String> set = new HashSet<>();
    for (int[] lamp : lamps) {
        // 注意重复的灯无需操作，只点亮一次
        if(set.contains(lamp[0] + " " + lamp[1])) continue;
        set.add(lamp[0] + " " + lamp[1]);
        rowMap.put(lamp[0], rowMap.getOrDefault(lamp[0], 0) + 1);
        colMap.put(lamp[1], colMap.getOrDefault(lamp[1], 0) + 1);
        leftMap.put(lamp[0] + lamp[1], leftMap.getOrDefault(lamp[0] + lamp[1], 0) + 1);
        rightMap.put(lamp[0] - lamp[1], rightMap.getOrDefault(lamp[0] - lamp[1], 0) + 1);
    }
    int[] res = new int[queries.length];
    int index = 0;
    for (int[] query : queries) {
        int x = query[0], y = query[1];
        if (rowMap.containsKey(x) && rowMap.get(x) > 0 || colMap.containsKey(y) && colMap.get(y) > 0 || leftMap.containsKey(x + y) && leftMap.get(x + y) > 0 || rightMap.containsKey(x - y) && rightMap.get(x - y) > 0)
            res[index] = 1;
        index++;
        for (int[] dir : dirs) {
            int nx = query[0] + dir[0], ny = query[1] + dir[1];
            boolean isRemove = set.remove(nx + " " + ny);
            if (isRemove) {
                rowMap.put(nx, rowMap.get(nx) - 1);
                colMap.put(ny, colMap.get(ny) - 1);
                leftMap.put(nx + ny, leftMap.get(nx + ny) - 1);
                rightMap.put(nx - ny, rightMap.get(nx - ny) - 1);
            }
        }
    }
    return res;
}

复杂度分析：a 是lamps的大小, b 是queries的大小
- 时间复杂度：$O(a+C*b)$，C为常数，本题为9，表示关闭周围9个灯
- 空间复杂度：$O(D*a)$，D为常数，本题为4，表示四个方向

本文作者： Chthollists
发布时间： 2022-02-08 16:23:17
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1001.网格照明
本文链接： https://chthollists.github.io/post/88e46cb4.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！