题目来源:https://leetcode-cn.com/problems/grid-illumination/
大致题意:
给定一个 n * n 的网格,一个灯泡数组用来表示灯泡的位置,一个查询数组查询该位置是否被照亮
每个灯泡会照亮它所在的行、列、对角线、反对角线的所有格子
每次查询时,若格子亮着,标记为 1,否则为 0。结束后,会关闭它周围八个格子的灯泡
返回查询结果的数组
思路
使用哈希表存下行、列、对角线、反对角线的灯泡数量,并用集合存下灯泡的坐标
查询时,查询对应位置所在的行、列、对角线、反对角线是否有灯泡,若有则标记当前查询结果,再遍历查询位置的周围格子,若有灯泡则关闭
哈希表
- 使用哈希表存下行、列、对角线、反对角线的灯泡数量,并用集合存下灯泡的坐标
- 遍历查询数组
- 查询对应位置所在的行、列、对角线、反对角线是否有灯泡,若有则标记当前查询结果,再遍历查询位置的周围格子,若有灯泡则关闭
代码:
public class GridIllumination {
public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
Map<Integer, Integer> row = new HashMap<>();
Map<Integer, Integer> col = new HashMap<>();
Map<Integer, Integer> diag = new HashMap<>();
Map<Integer, Integer> antiDiag = new HashMap<>();
Set<Long> lampSet = new HashSet<>();
// 存下行、列、对角线、反对角线的灯泡数量
for (int[] lamp : lamps) {
int x = lamp[0];
int y = lamp[1];
// 如果该位置已经存过,则跳过
if (!lampSet.add(hash(x, y))) {
continue;
}
row.put(x, row.getOrDefault(x, 0) + 1);
col.put(y, col.getOrDefault(y, 0) + 1);
diag.put(x - y, diag.getOrDefault(x - y, 0) + 1);
antiDiag.put(x + y, antiDiag.getOrDefault(x + y, 0) + 1);
}
int len = queries.length;
int[] ans = new int[len];
// 遍历查询数组
for (int i = 0; i < len; i++) {
int x = queries[i][0];
int y = queries[i][1];
// 若该位置被照亮
if (row.containsKey(x) || col.containsKey(y) || diag.containsKey(x - y) || antiDiag.containsKey(x + y)) {
ans[i] = 1;
}
// 遍历周围格子
for (int j = x - 1; j <= x + 1; j++) {
for (int k = y - 1; k <= y + 1; k++) {
if (!(j >= 0 && j < n && k >= 0 && k < n)) {
continue;
}
// 如果有灯泡,则删除
if (lampSet.remove(hash(j, k))) {
row.put(j, row.get(j) - 1);
if (row.get(j) == 0) {
row.remove(j);
}
col.put(k, col.get(k) - 1);
if (col.get(k) == 0) {
col.remove(k);
}
diag.put(j - k, diag.get(j - k) - 1);
if (diag.get(j - k) == 0) {
diag.remove(j - k);
}
antiDiag.put(j + k, antiDiag.get(j + k) - 1);
if (antiDiag.get(j + k) == 0) {
antiDiag.remove(j + k);
}
}
}
}
}
return ans;
}
// 自定义哈希函数
public long hash(int x, int y) {
return (long) x + ((long) y << 32);
}
}