题目描述
这是 LeetCode 上的 1001. 网格照明 ，难度为 困难。
Tag : 「模拟」、「哈希表」
在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。
给你一个由灯的位置组成的二维数组 lamps，其中 lamps[i] = [row_i, col_i]lamps[i]=[rowi,coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。
当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。
另给你一个二维数组 queries，其中 queries[j] = [row_j, col_j]queries[j]=[rowj,colj] 。对于第 jj 个查询，如果单元格 [row_j, col_j][rowj,colj] 是被照亮的，则查询结果为 11 ，否则为 00 。
在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[row_j][col_j]grid[rowj][colj] 上及相邻 88 个方向上（与单元格 grid[row_i][col_i]grid[rowi][coli] 共享角或边）的任何灯。
返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，11 表示照亮，00 表示未照亮。
示例 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 <= 10^91<=n<=109
- 0 <= lamps.length <= 200000<=lamps.length<=20000
- 0 <= queries.length <= 200000<=queries.length<=20000
- lamps[i].length == 2lamps[i].length==2
- 0 <= row_i, col_i < n0<=rowi,coli<n
- queries[j].length == 2queries[j].length==2
- 0 <= row_j, col_j < n0<=rowj,colj<n
哈希表 + 线映射
棋盘大小的数据范围为 n = 10^9n=109，硬模拟「亮灯」的操作必然会 TLE，而 lamps 和 queries 数据范围为 2000020000 是一个较为常见的突破口。
由于点亮每一盏灯，可以使得当前 行、列 和 对角线 的位置被照亮，行列可直接使用棋盘坐标的 (x, y)(x,y) 来代指，而对角线则可以使用「截距」来进行代指，即使用 x + yx+y 和 x - yx−y 进行代指。
分别使用四个「哈希表」row、col、left 和 right 来记录 行、列 和 对角线 的点亮情况（key 为线编号，value 为点亮次数）。
这样我们可以在 O(1)O(1) 的复杂度处理掉所有的 lamps[i]lamps[i]，某个位置被照亮的充要条件为：「当前位置所在行被点亮」或「当前位置所在列被点亮」或「当前位置所处的对角线被点亮」。
同时，由于每次查询后要进行「灭灯」操作（注意：灭灯只能灭有灯的位置，而不是灭有光的位置 🤣），因此我们还需要另外记录每个灯的位置，可以使用利用「二维转一维」的技巧进行编号：idx = x * n + yidx=x∗n+y，并使用 HashSet 进行记录（忽略重复的 lamps[i]lamps[i]）。
由于询问次数最多为 2000020000，因此直接在查询完成后模拟「灭灯」即可（访问自身及相邻格子，共 99 个），计算量为 2 * 10^52∗105 以内，可以接受。若某个位置存在灯，将其从 HashSet 中移除，并更新对应线的点亮情况。
代码：
class Solution { int[][] dirs = new int[][]{{0,0},{0,-1},{0,1},{-1,0},{-1,-1},{-1,1},{1,0},{1,-1},{1,1}}; public int[] gridIllumination(int n, int[][] lamps, int[][] queries) { long N = n; Map<Integer, Integer> row = new HashMap<>(), col = new HashMap<>(); Map<Integer, Integer> left = new HashMap<>(), right = new HashMap<>(); Set<Long> set = new HashSet<>(); for (int[] l : lamps) { int x = l[0], y = l[1]; int a = x + y, b = x - y; if (set.contains(x * N + y)) continue; increment(row, x); increment(col, y); increment(left, a); increment(right, b); set.add(x * N + y); } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; i++) { int[] q = queries[i]; int x = q[0], y = q[1]; int a = x + y, b = x - y; if (row.containsKey(x) || col.containsKey(y) || left.containsKey(a) || right.containsKey(b)) ans[i] = 1; for (int[] d : dirs) { int nx = x + d[0], ny = y + d[1]; int na = nx + ny, nb = nx - ny; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (set.contains(nx * N + ny)) { set.remove(nx * N + ny); decrement(row, nx); decrement(col, ny); decrement(left, na); decrement(right, nb); } } } return ans; } void increment(Map<Integer, Integer> map, int key) { map.put(key, map.getOrDefault(key, 0) + 1); } void decrement(Map<Integer, Integer> map, int key) { if (map.get(key) == 1) map.remove(key); else map.put(key, map.get(key) - 1); } } 复制代码
- 时间复杂度：令 lampslamps 长度为 aa，queriesqueries 长度为 bb，处理所有的 lamp[i]lamp[i] 复杂度为 O(a)O(a)，处理所有的 queries[j]queries[j] 复杂度为 O(C * b)O(C∗b)，其中 CC 为模拟灭灯时所联通的格子数量，固定为 99。整体复杂度为 O(a + C * b)O(a+C∗b)
- 空间复杂度：O(a)O(a)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1001 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
