Hard
题目描述
有一个大小为 n x n 的网格，网格中的每个单元格都有一个灯，初始时所有灯都是关闭的。
给你一个二维数组 lamps，其中 lamps[i] = [rowi, coli] 表示打开位于 grid[rowi][coli] 的灯。即使同一盏灯可能被列出多次，它也只会被打开一次。
当一盏灯被打开时，它会照亮其所在的单元格以及同一行、同一列和同一对角线上的所有其他单元格。
另外给你一个二维数组 queries，其中 queries[j] = [rowj, colj]。对于第 j 个查询，判断 grid[rowj][colj] 是否被照亮。在回答第 j 个查询后，关闭位于 grid[rowj][colj] 处的灯以及其 8 个相邻位置的灯（如果存在）。灯是相邻的，如果它的单元格与 grid[rowj][colj] 共享一条边或一个角。
返回一个整数数组 ans，其中 ans[j] 应该是 1（如果第 j 个查询中的单元格被照亮）或 0（如果灯没有照亮）。
示例 1：
输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[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^90 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == 20 <= rowi, coli < nqueries[j].length == 20 <= rowj, colj < n
解题思路
这道题的关键在于理解灯的照明范围和查询后的关闭操作。
核心思路：
- 照明机制：一盏灯会照亮同一行、同一列、两条对角线上的所有位置
- 计数策略：使用哈希表分别记录每行、每列、每条对角线上的灯数量
- 对角线表示：
- 主对角线：
row - col相同的位置在同一条主对角线 - 副对角线：
row + col相同的位置在同一条副对角线
- 主对角线：
算法步骤：
- 遍历所有灯的位置，在对应的行、列、对角线计数器中加1
- 对每个查询位置，检查其所在行、列、两条对角线是否有灯（计数>0）
- 查询后，关闭该位置及其8个相邻位置的灯，相应地减少计数器
优化要点：
- 使用哈希表存储灯的具体位置，便于关闭操作
- 只有当计数器为0时，该方向才不被照亮
- 关闭灯时需要检查灯是否真实存在
代码实现
class Solution {
public:
vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
unordered_map<int, int> rows, cols, diag1, diag2;
unordered_set<long long> lampSet;
// 添加所有灯
for (auto& lamp : lamps) {
int r = lamp[0], c = lamp[1];
long long pos = (long long)r * n + c;
if (lampSet.count(pos)) continue;
lampSet.insert(pos);
rows[r]++;
cols[c]++;
diag1[r - c]++;
diag2[r + c]++;
}
vector<int> result;
vector<vector<int>> dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};
for (auto& query : queries) {
int r = query[0], c = query[1];
// 检查是否被照亮
bool illuminated = rows[r] > 0 || cols[c] > 0 || diag1[r - c] > 0 || diag2[r + c] > 0;
result.push_back(illuminated ? 1 : 0);
// 关闭周围的灯
for (auto& dir : dirs) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
long long pos = (long long)nr * n + nc;
if (lampSet.count(pos)) {
lampSet.erase(pos);
rows[nr]--;
cols[nc]--;
diag1[nr - nc]--;
diag2[nr + nc]--;
}
}
}
}
return result;
}
};
class Solution:
def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
from collections import defaultdict
rows = defaultdict(int)
cols = defaultdict(int)
diag1 = defaultdict(int) # r - c
diag2 = defaultdict(int) # r + c
lamp_set = set()
# 添加所有灯
for r, c in lamps:
pos = r * n + c
if pos in lamp_set:
continue
lamp_set.add(pos)
rows[r] += 1
cols[c] += 1
diag1[r - c] += 1
diag2[r + c] += 1
result = []
directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1)]
for r, c in queries:
# 检查是否被照亮
illuminated = rows[r] > 0 or cols[c] > 0 or diag1[r - c] > 0 or diag2[r + c] > 0
result.append(1 if illuminated else 0)
# 关闭周围的灯
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n:
pos = nr * n + nc
if pos in lamp_set:
lamp_set.remove(pos)
rows[nr] -= 1
cols[nc] -= 1
diag1[nr - nc] -= 1
diag2[nr + nc] -= 1
return result
public class Solution {
public int[] GridIllumination(int n, int[][] lamps, int[][] queries) {
var rows = new Dictionary<int, int>();
var cols = new Dictionary<int, int>();
var diag1 = new Dictionary<int, int>();
var diag2 = new Dictionary<int, int>();
var lampSet = new HashSet<long>();
// 添加所有灯
foreach (var lamp in lamps) {
int r = lamp[0], c = lamp[1];
long pos = (long)r * n + c;
if (lampSet.Contains(pos)) continue;
lampSet.Add(pos);
rows[r] = rows.GetValueOrDefault(r) + 1;
cols[c] = cols.GetValueOrDefault(c) + 1;
diag1[r - c] = diag1.GetValueOrDefault(r - c) + 1;
diag2[r + c] = diag2.GetValueOrDefault(r + c) + 1;
}
var result = new List<int>();
int[,] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};
foreach (var query in queries) {
int r = query[0], c = query[1];
// 检查是否被照亮
bool illuminated = rows.GetValueOrDefault(r) > 0 ||
cols.GetValueOrDefault(c) > 0 ||
diag1.GetValueOrDefault(r - c) > 0 ||
diag2.GetValueOrDefault(r + c) > 0;
result.Add(illuminated ? 1 : 0);
// 关闭周围的灯
for (int i = 0; i < 9; i++) {
int nr = r + dirs[i, 0], nc = c + dirs[i, 1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
long pos = (long)nr * n + nc;
if (lampSet.Contains(pos)) {
lampSet.Remove(pos);
rows[nr]--;
cols[nc]--;
diag1[nr - nc]--;
diag2[nr + nc]--;
}
}
}
}
return result.ToArray();
}
}
var gridIllumination = function(n, lamps, queries) {
const rows = new Map();
const cols = new Map();
const diag1 = new Map();
const diag2 = new Map();
const lampSet = new Set();
// 添加所有灯
for (const [r, c] of lamps) {
const pos = r * n + c;
if (lampSet.has(pos)) continue;
lampSet.add(pos);
rows.set(r, (rows.get(r) || 0) + 1);
cols.set(c, (cols.get(c) || 0) + 1);
diag1.set(r - c, (diag1.get(r - c) || 0) + 1);
diag2.set(r + c, (diag2.get(r + c) || 0) + 1);
}
const result = [];
const directions = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[0,1],[1,-1],[1,0],[1,1]];
for (const [r, c] of queries) {
// 检查是否被照亮
const illuminated = (rows.get(r) || 0) > 0 ||
(cols.get(c) || 0) > 0 ||
(diag1.get(r - c) || 0) > 0 ||
(diag2.get(r + c) || 0) > 0;
result.push(illuminated ? 1 : 0);
// 关闭周围的灯
for (const [dr, dc] of directions) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
const pos = nr * n + nc;
if (lampSet.has(pos)) {
lampSet.delete(pos);
rows.set(nr, rows.get(nr) - 1);
cols.set(nc, cols.get(nc) - 1);
diag1.set(nr - nc, diag1.get(nr - nc) - 1);
diag2.set(nr + nc, diag2.get(nr + nc) - 1);
}
}
}
}
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(L + Q)，其中 L 是灯的数量，Q 是查询数量。每个灯和查询都是常数时间操作 |
| 空间复杂度 | O(L)，需要存储所有灯的位置和各方向的计数器 |
相关题目
- . N-Queens (Hard)