哈希表题目：网格照明

题目

标题和出处

标题：网格照明

出处：1001. 网格照明

难度

6 级

题目描述

要求

在 $\text{n}\times \text{n}$ 的二维网格 $\text{grid}$ 上，每个单元格都有一盏灯，最初灯都处于关闭状态。

给你一个二维数组 $\text{lamps}$ 表示灯的位置，其中 ${\text{lamps[i] = [row}}_{\text{i}}{\text{, col}}_{\text{i}}\text{]}$ 表示打开位于 ${\text{grid[row}}_{\text{i}}{\text{][col}}_{\text{i}}\text{]}$ 的灯。即使同一盏灯在数组中出现多次，也是打开这盏灯。

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

给你另一个二维数组 $\text{queries}$，其中 ${\text{queries[j] = [row}}_{\text{j}}{\text{, col}}_{\text{j}}\text{]}$。对于第 $\text{j}$ 次查询，判断 ${\text{grid[row}}_{\text{j}}{\text{][col}}_{\text{j}}\text{]}$ 是否被照亮。在回答第 $\text{j}$ 次查询之后，关闭位于 ${\text{grid[row}}_{\text{j}}{\text{][col}}_{\text{j}}\text{]}$ 的灯和相邻的 $\text{8}$ 盏灯（如果存在）。如果一盏灯和 ${\text{grid[row}}_{\text{j}}{\text{][col}}_{\text{j}}\text{]}$ 共享边或角，则这盏灯是相邻的。

返回答案数组 $\text{ans}$，如果第 $\text{j}$ 次查询的单元格被照亮，则 $\text{ans[j]}$ 是 $\text{1}$，否则 $\text{ans[j]}$ 是 $\text{0}$。

示例

示例 1：

输入：$\text{n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]}$
输出：$\text{[1,0]}$
解释：最初所有灯都是关闭的。上图中可以看到打开位于 $\text{grid[0][0]}$ 的灯然后打开位于 $\text{grid[4][4]}$ 的灯之后的网格。
第 $\text{0}$ 次查询检查 $\text{grid[1][1]}$ 是否被照亮（蓝色方框）。该单元格被照亮，所以 $\text{ans[0] = 1}$。然后，关闭红色方框中的所有灯。

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

示例 2：

输入：$\text{n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]}$
输出：$\text{[1,1]}$

示例 3：

输入：$\text{n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]}$
输出：$\text{[1,1,0]}$

数据范围

• $\text{1}\le \text{n}\le {\text{10}}^{\text{9}}$
• $\text{0}\le \text{lamps.length}\le \text{20000}$
• $\text{0}\le \text{queries.length}\le \text{20000}$
• $\text{lamps[i].length}=\text{2}$
• $\text{0}\le {\text{row}}_{\text{i}}{\text{, col}}_{\text{i}}<\text{n}$
• $\text{queries[i].length}=\text{2}$
• $\text{0}\le {\text{row}}_{\text{j}}{\text{, col}}_{\text{j}}<\text{n}$

解法

思路和算法

每个单元格都位于一行、一列和两条对角线上。一个单元格被照亮，等价于至少有一盏打开的灯和该单元格位于同一行、同一列或者同一条对角线上。因此，为了快速判断一个单元格是否被照亮，需要记录每一行、每一列和两个方向的每一条对角线上打开的灯的数量，可以使用哈希表记录。

维护四个哈希表，分别记录每一行打开的灯的数量、每一列打开的灯的数量、每一条方向一对角线上打开的灯的数量和每一条方向二对角线上打开的灯的数量，其中方向一对角线表示从左上到右下方向的对角线，方向二对角线表示从左下到右上方向的对角线。这四个哈希表分别称为行哈希表、列哈希表、对角线一哈希表和对角线二哈希表。

当 $0\le \text{row},\text{col}<n$ 时，如果位于第 $\text{row}$ 行第 $\text{col}$ 列的灯被打开，则需要将这盏灯存入四个哈希表。

• 由于灯所在的行是 $\text{row}$，因此在行哈希表中将 $\text{row}$ 对应的数量加 $1$；

• 由于灯所在的列是 $\text{col}$，因此在列哈希表中将 $\text{col}$ 对应的数量加 $1$；

• 由于在方向一对角线上，如果向左上移动一步则 $\text{row}$ 和 $\text{col}$ 同时减 $1$，如果向右下移动一步则 $\text{row}$ 和 $\text{col}$ 同时加 $1$，因此在同一条方向一对角线上的每个单元格满足 $\text{row}-\text{col}$ 是定值，在对角线一哈希表中将 $\text{row}-\text{col}$ 对应的数量加 $1$；

• 由于在方向二对角线上，如果向左下移动一步则 $\text{row}$ 加 $1$ 且 $\text{col}$ 减 $1$，如果向右上移动一步则 $\text{row}$ 减 $1$ 且 $\text{col}$ 加 $1$，因此在同一条方向二对角线上的每个单元格满足 $\text{row}+\text{col}$ 是定值，在对角线二哈希表中将 $\text{row}+\text{col}$ 对应的数量加 $1$。

数组 $\text{lamps}$ 表示打开的灯的位置。遍历数组 $\text{lamps}$，对其中的每一个位置 $[\text{row},\text{col}]$，使用该位置更新四个哈希表。

由于数组 $\text{lamps}$ 中可能存在重复的位置，因此需要去重，避免同一个位置的灯被重复计算。去重的方法是使用哈希集合存储所有打开的灯的位置，哈希集合可以确保同一个位置只被加入一次。由于每一盏灯所在的行 $\text{row}$ 和列 $\text{col}$ 都是整数且都在范围 $[0,n-1]$ 内，因此可以定义哈希函数 $f(\text{row},\text{col})=\text{row}\times n+\text{col}$，该哈希函数可以确保不同位置对应的哈希值不同。

假设存在位置 $[{\text{row}}_1,{\text{col}}_1]$ 和 $[{\text{row}}_2,{\text{col}}_2]$ 满足 $f({\text{row}}_1,{\text{col}}_1)=f({\text{row}}_2,{\text{col}}_2)$，则有 ${\text{row}}_1\times n+{\text{col}}_1={\text{row}}_2\times n+{\text{col}}_2$，即 $({\text{row}}_1-{\text{row}}_2)\times n={\text{col}}_2-{\text{col}}_1$。由于 $|{\text{row}}_1-{\text{row}}_2|<n$，$|{\text{col}}_2-{\text{col}}_1|<n$，且位置都是整数，因此一定有 ${\text{row}}_1-{\text{row}}_2={\text{col}}_2-{\text{col}}_1=0$，$[{\text{row}}_1,{\text{col}}_1]$ 和 $[{\text{row}}_2,{\text{col}}_2]$ 是相同的位置。

定义哈希函数之后，根据哈希函数计算数组 $\text{lamps}$ 中的每个位置对应的哈希值。对于每个位置，只有当该位置的哈希值不在哈希集合中时，才将哈希值存入哈希集合，并使用该位置更新四个哈希表。

查询时，对于数组 $\text{queries}$ 中的每个位置 $[\text{row},\text{col}]$，首先判断该位置在四个哈希表中对应的数量是否大于 $0$，得到查询结果，然后将该位置和全部相邻位置的灯都关闭。具体做法如下。

1. 在行哈希表中得到 $\text{row}$ 的数量、在列哈希表中得到 $\text{col}$ 的数量、在对角线一哈希表中得到 $\text{row}-\text{col}$ 的数量、在对角线二哈希表中得到 $\text{row}+\text{col}$ 的数量，如果该位置在四条线上对应的数量至少有一个大于 $0$ 则查询结果是 $1$，如果该位置在四条线上对应的数量都是 $0$ 则查询结果是 $0$。

2. 遍历位置 $[\text{row},\text{col}]$ 和全部相邻位置，对于每个位置，如果该位置对应的哈希值在哈希集合中，则说明该位置的灯处于打开状态，需要关闭，将该位置对应的哈希值从哈希集合中删除，并将该位置在四个哈希表中对应的数量分别减 $1$。

查询时的关灯操作可以优化。如果一个单元格所在位置和全部相邻位置中至少有一盏灯打开，则该单元格一定被照亮，因此如果一个单元格没有被照亮，则该单元格所在位置和全部相邻位置的灯一定都处于关闭状态。只有当查询结果是 $1$ 时，才需要执行关灯操作。

代码

class Solution {public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {Set<Long> set = new HashSet<Long>();Map<Integer, Integer> rowMap = new HashMap<Integer, Integer>();Map<Integer, Integer> columnMap = new HashMap<Integer, Integer>();Map<Integer, Integer> diagonal1Map = new HashMap<Integer, Integer>();Map<Integer, Integer> diagonal2Map = new HashMap<Integer, Integer>();for (int[] lamp : lamps) {int row = lamp[0], column = lamp[1];long position = (long) row * n + column;if (set.add(position)) {rowMap.put(row, rowMap.getOrDefault(row, 0) + 1);columnMap.put(column, columnMap.getOrDefault(column, 0) + 1);int diagonal1 = row - column;diagonal1Map.put(diagonal1, diagonal1Map.getOrDefault(diagonal1, 0) + 1);int diagonal2 = row + column;diagonal2Map.put(diagonal2, diagonal2Map.getOrDefault(diagonal2, 0) + 1);}}int[][] directions = {{0, 0}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};int queriesCount = queries.length;int[] ans = new int[queriesCount];for (int j = 0; j < queriesCount; j++) {int[] query = queries[j];int queryRow = query[0], queryColumn = query[1];boolean flag = rowMap.containsKey(queryRow) || columnMap.containsKey(queryColumn) || diagonal1Map.containsKey(queryRow - queryColumn) || diagonal2Map.containsKey(queryRow + queryColumn);if (flag) {ans[j] = 1;for (int[] direction : directions) {int row = queryRow + direction[0], column = queryColumn + direction[1];int diagonal1 = row - column, diagonal2 = row + column;if (row >= 0 && row < n && column >= 0 && column < n) {long position = (long) row * n + column;if (set.remove(position)) {rowMap.put(row, rowMap.get(row) - 1);if (rowMap.get(row) == 0) {rowMap.remove(row);}columnMap.put(column, columnMap.get(column) - 1);if (columnMap.get(column) == 0) {columnMap.remove(column);}diagonal1Map.put(diagonal1, diagonal1Map.get(diagonal1) - 1);if (diagonal1Map.get(diagonal1) == 0) {diagonal1Map.remove(diagonal1);}diagonal2Map.put(diagonal2, diagonal2Map.get(diagonal2) - 1);if (diagonal2Map.get(diagonal2) == 0) {diagonal2Map.remove(diagonal2);}}}}}}return ans;}
}

复杂度分析

• 时间复杂度：$O(l+q)$，其中 $l$ 是数组 $\text{lamps}$ 的长度，$q$ 是数组 $\text{queries}$ 的长度。需要遍历数组 $\text{lamps}$，对于每个打开的灯的位置，将该位置存入哈希集合以及更新四个哈希表的时间都是 $O(1)$，然后需要遍历数组 $\text{queries}$，对于每个查询，计算查询结果以及更新哈希表和哈希集合的时间都是 $O(1)$，因此总时间复杂度是 $O(l+q)$。

• 空间复杂度：$O(l)$，其中 $l$ 是数组 $\text{lamps}$ 的长度。需要使用四个哈希表记录打开的灯的数量以及使用哈希集合存储打开的灯的位置，哈希表和哈希集合的空间复杂度都是 $O(l)$。注意返回值不计入空间复杂度。