Leetcode每日一题 —— 3534. 针对图的路径存在性查询 II

思路

参考昨天的题目，今天题目第一件事肯定是排序，并记录定位。

一开始我是用快慢指针来确定每个节点(排序后)能到达的最大节点，但是在遍历queries的时候TLE了。

那么现在的问题就是如何加速了。首先想到的是把src能达到的所有步数的长度都存起来(借助指针可以只存一遍让时间复杂度降低)，然后二分去查找，但是这样还挺麻烦的，反过来想，我们可以逆向二分也就是借助st表的概念，直接存幂次的步数。这样时间复杂度应该就没问题了。

class Solution {

    public int[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {

        Integer[] idx = new Integer[n];

        for (int i = 0; i < n; i++) {

            idx[i] = i;

        }

        Arrays.sort(idx, Comparator.comparingInt(i -> nums[i]));

        int[] pos = new int[n];

        for (int i = 0; i < n; i++) {

            pos[idx[i]] = i;

        }



        int[] right = new int[n];

        int fast = 0;

        for (int slow = 0; slow < n; slow++) {

            while (fast < n && nums[idx[fast]] - nums[idx[slow]] <= maxDiff) {

                fast++;

            }

            right[slow] = fast - 1;

        }



        int[] ans = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {

            int src = pos[queries[i][0]];

            int dist = pos[queries[i][1]];

            if (src > dist) {

                int t = src;

                src = dist;

                dist = t;

            }

            if (src == dist) {

                continue;

            }

            int step = 1;

            while (right[src] < dist) {

                if (right[src] == src) {

                    step = -1;

                    break;

                }

                src = right[src];

                step++;

            }

            ans[i] = step;

        }

        return ans;

    }

}

代码

class Solution {

    public int[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {

        Integer[] idx = new Integer[n];

        for (int i = 0; i < n; i++) {

            idx[i] = i;

        }

        Arrays.sort(idx, Comparator.comparingInt(i -> nums[i]));

        int[] pos = new int[n];

        for (int i = 0; i < n; i++) {

            pos[idx[i]] = i;

        }



        int maxPow = 32 - Integer.numberOfLeadingZeros(n);

        int[][] right = new int[n][maxPow];

        int fast = 0;

        for (int slow = 0; slow < n; slow++) {

            while (fast < n && nums[idx[fast]] - nums[idx[slow]] <= maxDiff) {

                fast++;

            }

            right[slow][0] = fast - 1;

        }

        for (int j = 1; j < maxPow; j++) {

            for (int i = 0; i < n; i++) {

                right[i][j] = right[right[i][j - 1]][j - 1];

            }

        }



        int[] ans = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {

            int src = pos[queries[i][0]];

            int dist = pos[queries[i][1]];

            if (src > dist) {

                int t = src;

                src = dist;

                dist = t;

            }

            if (src == dist) {

                continue;

            }

            int step = 0;

            for (int j = maxPow - 1; j >= 0; j--) {

                if (right[src][j] < dist) {

                    src = right[src][j];

                    step |= 1 << j;

                }

            }

            ans[i] = right[src][0] < dist ? -1 : step + 1;

        }

        return ans;

    }

}