网格照明
难度:
标签:
题目描述
在大小为 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
代码结果
运行时间: 173 ms, 内存: 36.2 MB
解释
方法:
该题解使用了字典来存储灯的位置信息，通过记录每一行、每一列以及两个对角线上灯的数量，可以快速判断某个位置是否被照亮。对于每个查询，先判断该位置是否被照亮，如果被照亮则将结果记为1，并关闭该位置及其相邻8个方向上的灯；如果未被照亮则将结果记为0。最后返回所有查询的结果。
时间复杂度:
O(m+n)
空间复杂度:
O(m)
代码细节讲解
🦆
如何保证查询时，字典中的灯数量信息是准确的，特别是在多次关闭操作后？
▷🦆
在关闭相邻灯的操作中，如果一个灯被多次列为关闭（因其在多个查询的相邻位置），这种情况如何处理，是否有重复关闭的风险？
▷🦆
为什么在判断一个位置是否被照亮时，只需要检查该位置的行、列和对角线上的灯的数量，而不检查具体的灯位置？
▷🦆
在多个灯可能照亮同一行或列的情况下，单纯减少行或列的计数器（在关闭灯时）是否足以正确表示该行或列的照明状态？
▷相关问题
N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
提示：
1 <= n <= 9