Grid Illumination

2019-07-07 16:53:31

问题描述：

问题求解：

本题和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);

                }

            }

        }

    }

巴特西

Grid Illumination

最新文章

热门文章