LeetCode 题解工作台
网格照明
在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。 给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [row i , col i ] 表示 打开 位于 grid[row i ][col i ] 的灯。即便同一盏灯可能在 lamps…
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
假设一盏灯的坐标为 $(x, y)$，那么它所在的行的数值为 ，列的数值为 ，正对角线的数值为 ，反对角线的数值为 。确定某一直线的唯一数值标识后，我们就可以通过哈希表来记录某一直线所拥有的灯的数目。 我们遍历数组 ，将当前遍历到的灯所在的行、列和正、反对角线拥有灯的数目分别加 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
在大小为 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 <= 1090 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == 20 <= rowi, coli < nqueries[j].length == 20 <= rowj, colj < n
解题思路
方法一：哈希表
假设一盏灯的坐标为 ，那么它所在的行的数值为 ，列的数值为 ，正对角线的数值为 ，反对角线的数值为 。确定某一直线的唯一数值标识后，我们就可以通过哈希表来记录某一直线所拥有的灯的数目。
我们遍历数组 ，将当前遍历到的灯所在的行、列和正、反对角线拥有灯的数目分别加 。
注意，在处理 时，需要进行去重，因为我们将重复的灯看作同一盏灯。
接下来，我们遍历 queries，判断当前查询点所在的行，列和正、反对角线是否有灯，如果有，则置 ，即该点在查询时是被照亮的。然后进行关闭操作，查找查询点所在的八近邻点及它本身是否有灯，如果有，将该点所在的行、列和正、反对角线的灯数目分别减 ，并且将灯从网格中去掉。
最后，返回答案数组即可。
时间复杂度 ，其中 和 分别为数组 和 的长度。
class Solution:
def gridIllumination(
self, n: int, lamps: List[List[int]], queries: List[List[int]]
) -> List[int]:
s = {(i, j) for i, j in lamps}
row, col, diag1, diag2 = Counter(), Counter(), Counter(), Counter()
for i, j in s:
row[i] += 1
col[j] += 1
diag1[i - j] += 1
diag2[i + j] += 1
ans = [0] * len(queries)
for k, (i, j) in enumerate(queries):
if row[i] or col[j] or diag1[i - j] or diag2[i + j]:
ans[k] = 1
for x in range(i - 1, i + 2):
for y in range(j - 1, j + 2):
if (x, y) in s:
s.remove((x, y))
row[x] -= 1
col[y] -= 1
diag1[x - y] -= 1
diag2[x + y] -= 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate optimize the solution when lamps are sparse in the grid?
- question_mark
Is the candidate able to explain the trade-offs of storing lamp positions in hash sets versus a 2D array?
- question_mark
How does the candidate handle large grid sizes with respect to time and space complexity?
常见陷阱
外企场景- error
Not using hash sets for row, column, and diagonal tracking, leading to inefficient query resolution.
- error
Failure to remove lamps from the hash sets after processing queries, which can affect the results of subsequent queries.
- error
Overcomplicating the grid updates when dealing with large values of n, leading to unnecessary computations.
进阶变体
外企场景- arrow_right_alt
Handling queries where multiple lamps are turned off at once, affecting multiple rows, columns, and diagonals.
- arrow_right_alt
Adapting the solution to handle multiple grid sizes more efficiently.
- arrow_right_alt
Optimizing memory usage when handling large n values by compressing lamp positions.