JAVA练习97-网格照明

在大小为 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 <= 10^90 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == 20 <= rowi, coli < nqueries[j].length == 20 <= rowj, colj < n分析：

方法：哈希表

因为 n 最大为 10^9，如果用二维数组，空间复杂度最大就是 10^18，一定会超内存，那么我们可以用 哈希表 的方式来存储每一行，列，两对角线的灯的个数，这样空间复杂度最大就为 10^9，行用横坐标，列用纵坐标，左对角线用横纵之和，右对角线用横纵之差，关灯的时候只需要所有哈希表对应值减一就可以了。

关于 lamps，如果每次找灯都遍历一次，太浪费时间，因此我们将二维数组转化为一维的集合，假设查找的坐标为 （i，j），lamps 边长为 n，那么就可以表示为 i * n + j，这样每次找灯只需要调用集合相关方法即可，还可以防止哈希表存储时出现重复灯的情况。

关于找周围的灯，我们可以定义一个二维数组表示自身和周围八格的横纵坐标的差值，找灯时只需要遍历该数组，将差值加到当前坐标即可。

时间复杂度：O(m + n)        m，n 为 lamps，queries 的长度
空间复杂度：O(m)

class Solution { public int[] gridIllumination(int n, int[][] lamps, int[][] queries) { //创建HashMap分别存储 行，列，左右对角线的灯 HashMap row = new HashMap<>(), col = new HashMap<>(), left = new HashMap<>(), right = new HashMap<>(); //创建集合，存储灯 HashSet set = new HashSet<>(); //遍历，存储灯 for(int[] lamp: lamps){ //避免添加多余的灯 if(set.contains(lamp[0] * (long) n + lamp[1])){ continue; } //行 storage(row, lamp[0]); //列 storage(col, lamp[1]); //左对角线 storage(left, lamp[0] + lamp[1]); //右对角线 storage(right, lamp[0] - lamp[1]); //二维转一维存储 set.add(lamp[0] * (long) n + lamp[1]); } //记录照明情况 int[] res = new int[queries.length]; //定义当前格和周围八格 int[][] surrounds = new int[][]{{0, 0}, {0, -1}, {0, 1}, {-1, 0}, {-1, -1}, {-1, 1}, {1, 0}, {1, 1}, {1, -1}}; //遍历 queries 数组，记录照明情况，关灯 for(int i = 0; i < queries.length; ++i){ //记录两数 int j = queries[i][0], k = queries[i][1]; //判断是否被照明 if(row.containsKey(j) || col.containsKey(k) || left.containsKey(j + k) || right.containsKey(j - k)){ res[i] = 1; }else{ res[i] = 0; } //关灯 for(int[] sur: surrounds){ //当前位置 int a = j + sur[0], b = k + sur[1]; //越界 if(a < 0 || b < 0 || a > n-1 || b > n-1){ continue; } //有灯，关灯 if(set.contains(a * (long) n + b)){ //删除此灯 set.remove(a * (long) n + b); //行 close(row, a); //列 close(col, b); //左对角线 close(left, a + b); //右对角线 close(right, a - b); } } } return res; } //存储灯的方法 public void storage(HashMap map, int key){ map.put(key, map.getOrDefault(key, 0) + 1); } //关灯 public void close(HashMap map, int key){ if(map.get(key) == 1){ map.remove(key); } else{ map.put(key, map.get(key)-1); } }}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/grid-illumination