leetcode1001. 网格照明(hard)

解题思路

代码
力扣链接

官方题解
大佬题解

哈希表 代码

class Solution {
    static final int[][] DIRS = new int[][]{{0, 0}, {0,1},{0,-1},{1,0},{-1,0},{-1,-1},{1,1},{1,-1},{-1,1}};

    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        //使用集合存储开启的灯的二维坐标转成一维的值
        Set set = new HashSet<>();
        //存储每个灯能够照亮的行,列,正对角线,反对角线,及其被照亮的次数
        Map row = new HashMap<>();
        Map col = new HashMap<>();
        Map z = new HashMap<>();
        Map f = new HashMap<>();

        for (int[] lamp : lamps) {
            int x = lamp[0];
            int y = lamp[1];
            if (!set.contains(n * x + y)) {
                increment(row, x);
                increment(col, y);
                increment(z, x -y);
                increment(f, x + y);
                set.add(n * x + y);
            }
        }

        int size = queries.length;
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            int x = queries[i][0];
            int y = queries[i][1];
            if (row.containsKey(x) || col.containsKey(y) || z.containsKey(x - y) || f.containsKey(x + y)) {
                res[i] = 1;
            }
            //关灯
            for (int[] dir : DIRS) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (set.contains(n * nx + ny)) {
                        set.remove(n * nx + ny);
                        decrement(row, nx);
                        decrement(col, ny);
                        decrement(z, nx - ny);
                        decrement(f, nx + ny);
                    }
                }
            }
            
        }
        return res;
    }

    void increment(Map map, int key) {
        map.put(key, map.getOrDefault(key, 0) + 1);
    }
    void decrement(Map map, int key) {
        if (map.get(key) != null) {
            if (map.get(key) == 1) {
                map.remove(key);
            } else {
                map.put(key, map.get(key) - 1);
            }
        }
    }
}