Grid Illumination

淡淡的烟草味﹌ 2021-12-03 20:15 240阅读 0赞

2019-07-07 16:53:31

**问题描述：**

![1187314-20190707165431911-618283028.png][]

![1187314-20190707165449994-1462771419.png][]

**问题求解：**

本题和n后问题很类似，所以最初的时候就直接套了n后的板子，MLE。

public int[] gridIllumination(int N, int[][] lamps, int[][] queries) {
            int[] rows = new int[N];
            int[] cols = new int[N];
            int[] diag1 = new int[2 * N - 1];
            int[] diag2 = new int[2 * N - 1];
            Set<String> set = new HashSet<>();
            for (int[] lamp : lamps) {
                int x = lamp[0];
                int y = lamp[1];
                rows[x]++;
                cols[y]++;
                diag1[x + y]++;
                diag2[N - 1 - x + y]++;
                set.add(String.valueOf(x) + "_" + String.valueOf(y));
            }
            int n = queries.length;
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                int[] q = queries[i];
                int x = q[0];
                int y = q[1];
                if (rows[x] > 0 || cols[y] > 0 || diag1[x + y] > 0 || diag2[N - 1 - x + y] > 0) 
                    res[i] = 1;
                else res[i] = 0;
                helper(x, y, set, rows, cols, diag1, diag2, N);
            }
            return res;
        }
        
        private void helper(int x, int y, Set<String> set, int[] rows, int[] cols, int[] diag1, int[] diag2, int N) {
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    int pi = x + i;
                    int pj = y + j;
                    if (pi < 0 || pi >= N || pj < 0 || pj >= N) continue;
                    String cur = String.valueOf(pi) + "_" + String.valueOf(pj);
                    if (set.contains(cur)) {
                        set.remove(cur);
                        rows[pi]--;
                        cols[pj]--;
                        diag1[pi + pj]--;
                        diag2[N - 1 - pi + pj]--;
                    }
                }
            }
        }

那么本题的核心就是如何降低空间复杂度了，如何做呢？

> 降低空间复杂度有两种常用的技巧：
> 
> 1. 将数组转为HashMap，这样就可以在大量稀疏的数组中提取到有用的信息，避免无用的信息。
> 
> 2. 如何保存已经点亮的位置，这里采用字符串的处理显然是低效的，最好的方法是采用位操作的方式，使用long将两个int拼接起来达到区分的效果。

public int[] gridIllumination(int N, int[][] lamps, int[][] queries) {
            HashMap<Integer, Integer> rows, cols, diag1, diag2;
            rows = new HashMap<Integer, Integer>();
            cols = new HashMap<Integer, Integer>();
            diag1 = new HashMap<Integer,Integer>();
            diag2 = new HashMap<Integer, Integer>();
            Set<Long> set = new HashSet<>();
            for (int[] lamp : lamps) {
                int x = lamp[0];
                int y = lamp[1];
                rows.put(x, rows.getOrDefault(x, 0) + 1);
                cols.put(y, cols.getOrDefault(y, 0) + 1);
                diag1.put(x + y, diag1.getOrDefault(x + y, 0) + 1);
                diag2.put(N - 1 - x + y, diag2.getOrDefault(N - 1 - x + y, 0) + 1);
                set.add((long)x << 32 | (long)y);
            }
            int n = queries.length;
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                int[] q = queries[i];
                int x = q[0];
                int y = q[1];
                if (rows.getOrDefault(x, 0) > 0 || cols.getOrDefault(y, 0) > 0 || diag1.getOrDefault(x + y, 0) > 0 || diag2.getOrDefault(N - 1 - x + y, 0) > 0) 
                    res[i] = 1;
                else res[i] = 0;
                helper(x, y, set, rows, cols, diag1, diag2, N);
            }
            return res;
        }
        
        private void helper(int x, int y, Set<Long> set,  HashMap<Integer, Integer> rows, HashMap<Integer, Integer> cols, HashMap<Integer, Integer> diag1, HashMap<Integer, Integer> diag2, int N) {
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    int pi = x + i;
                    int pj = y + j;
                    if (pi < 0 || pi >= N || pj < 0 || pj >= N) continue;
                    long cur = (long)pi << 32 | pj;
                    if (set.contains(cur)) {
                        set.remove(cur);
                        rows.put(pi, rows.get(pi) - 1);
                        cols.put(pj, cols.get(pj) - 1);
                        diag1.put(pi + pj, diag1.get(pi + pj) - 1);
                        diag2.put(N - 1 - pi + pj, diag2.get(N - 1 - pi + pj) - 1);
                    }
                }
            }
        }

转载于:https://www.cnblogs.com/TIMHY/p/11146784.html

[1187314-20190707165431911-618283028.png]: /images/20211203/2579aa1c29bd4326af85c28a5c021d66.png
[1187314-20190707165449994-1462771419.png]: /images/20211203/d6524b30d4294527b491f494b69f6803.png