2022.02.08 - 233.网格照明

1. 题目2. 思路

(1) 哈希表 3. 代码

利用哈希表存储每个灯的位置以及被照亮的行、列、正对角线、反对角线上灯的个数，查询时判断该位置是否处于某个被照亮的行、列、正对角线、反对角线上即可。 3. 代码

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Set set = new HashSet<>();
        Map row = new HashMap<>();
        Map col = new HashMap<>();
        Map line1 = new HashMap<>();
        Map line2 = new HashMap<>();
        for (int[] lamp : lamps) {
            if (!set.add(hash(lamp[0], lamp[1]))) {
                continue;
            }
            row.put(lamp[0], row.getOrDefault(lamp[0], 0) + 1);
            col.put(lamp[1], col.getOrDefault(lamp[1], 0) + 1);
            int l1 = lamp[0] - lamp[1];
            int l2 = lamp[0] + lamp[1];
            line1.put(l1, line1.getOrDefault(l1, 0) + 1);
            line2.put(l2, line2.getOrDefault(l2, 0) + 1);
        }
        int m = queries.length;
        int[] res = new int[m];
        for (int i = 0; i < m; i++) {
            int x = queries[i][0];
            int y = queries[i][1];
            if (row.getOrDefault(x, 0) > 0) {
                res[i] = 1;
            } else if (col.getOrDefault(y, 0) > 0) {
                res[i] = 1;
            } else if (line1.getOrDefault(x - y, 0) > 0) {
                res[i] = 1;
            } else if (line2.getOrDefault(x + y, 0) > 0) {
                res[i] = 1;
            }
            for (int j = x - 1; j <= x + 1; j++) {
                for (int k = y - 1; k <= y + 1; k++) {
                    if (j < 0 || k < 0 || j >= n || k >= n) {
                        continue;
                    }
                    if (set.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);
                        }
                        int l1 = j - k;
                        line1.put(l1, line1.get(l1) - 1);
                        if (line1.get(l1) == 0) {
                            line1.remove(l1);
                        }
                        int l2 = j + k;
                        line2.put(l2, line2.get(l2) - 1);
                        if (line2.get(l2) == 0) {
                            line2.remove(l2);
                        }
                    }
                }
            }
        }
        return res;
    }

    public long hash(int x, int y) {
        return ((long) x << 32) + (long) y;
    }
}