LeetCode.1001 网格照明

题目链接

思路

哈希/字典

对于每个灯，记录这个灯的位置，在x行y列，对行和列分别记录，并记录两条对角线的灯的个数
对于每次查询，先看在这一行和这一列是否存在灯，然后查询对角线
对每一行/列，只需检查这一行/列有无灯即可，这里即判断SortedSet/HashSet中是否有元素
对于对角线，两条对角线的特点为和/差为定值，可以通过和差来判断该对角线上有无灯

删除时，对包括自身在内的周围9个位置检测是否有灯，对四个字典中的灯进行删除
对于行/列，删除时只需删除对应的元素即可，只要插入时有判重就没有问题
对于对角线处理可能有些麻烦，这里的处理方法是添加时不是判断是否有灯而是对对角线上的灯进行计数，而删除时是在删除行/列的基础上进行的，因为对行/列的字典可以检测到具体的位置，若检测到该位置有灯，则对其两条对角线上删除一个灯即可

代码

public class Solution {
    public bool Judge(int x, int y, int n) {
        return 0 <= x && x < n && 0 <= y && y < n;
    }
    public int[] GridIllumination(int n, int[][] lamps, int[][] queries) {
        Dictionary<int, SortedSet<int>> onx = new Dictionary<int, SortedSet<int>>();
        Dictionary<int, SortedSet<int>> ony = new Dictionary<int, SortedSet<int>>();
        Dictionary<int, int> plus = new Dictionary<int, int>();
        Dictionary<int, int> sub = new Dictionary<int, int>(); 
        for (int i = 0; i < lamps.Length; i++) {
            bool have = false;
            int x = lamps[i][0], y = lamps[i][1];
            if (!onx.ContainsKey(x)) {
                SortedSet<int> set = new SortedSet<int>();
                set.Add(y);
                onx.Add(x, set);
            } else {
                if (!onx[x].Contains(y)) {
                    onx[x].Add(y);
                } else {
                    have = true;
                }
            }
            if (!ony.ContainsKey(y)) {
                SortedSet<int> set = new SortedSet<int>();
                set.Add(x);
                ony.Add(y, set);
            } else {
                if (!ony[y].Contains(x)) {
                    ony[y].Add(x);
                } else {
                    have = true;
                }
            }
            if (plus.ContainsKey(x + y)) {
                if (!have)  plus[x + y]++;
            } else {
                plus.Add(x + y, 1);
            }
            if (sub.ContainsKey(x - y)) {
                if (!have)  sub[x - y]++;
            } else {
                sub.Add(x - y, 1);
            }
        }
        
        int[] ans = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int x = queries[i][0], y = queries[i][1];
            ans[i] = 0;
            if (onx.ContainsKey(x) && onx[x].Count != 0) {
                ans[i] = 1;
            } else if (ony.ContainsKey(y) && ony[y].Count != 0) {
                ans[i] = 1;
            } else if (plus.ContainsKey(x + y) && plus[x + y] != 0) {
                ans[i] = 1;
            } else if (sub.ContainsKey(x - y) && sub[x - y] != 0) {
                ans [i] = 1;
            }

            for (int j = x - 1; j <= x + 1; j++) {
                for (int k = y - 1; k <= y + 1; k++) {
                    if (!judge(j, k, n))    continue;
                    if (onx.ContainsKey(j) && onx[j].Contains(k)) {
                        onx[j].Remove(k);
                        if (onx[j].Count == 0) {
                            onx.Remove(j);
                        }
                        if (plus.ContainsKey(j + k)) {
                            plus[j + k]--;
                            if (plus[j + k] == 0) {
                                plus.Remove(j + k);
                            }
                        }
                        if (sub.ContainsKey(j - k)) {
                            sub[j - k]--;
                            if (sub[j - k] == 0) {
                                sub.Remove(j - k);
                            }
                        }
                    }
                    if (ony.ContainsKey(k) && ony[k].Contains(j)) {
                        ony[k].Remove(j);
                        if (ony[k].Count == 0) {
                            ony.Remove(k);
                        }
                    }
                }
            }
        }
        return ans;
    }
}