标签： hard

目标

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

实现 TreeAncestor 类：

• TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
• getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

说明：

• 1 <= k <= n <= 5 * 10^4
• parent[0] == -1 表示编号为 0 的节点是根节点。
• 对于所有的 0 < i < n ，0 <= parent[i] < n 总成立
• 0 <= node < n
• 至多查询 5 * 10^4 次

思路

这个题让我们维护一个数据结构，来查找树中任意节点的第k个祖先节点。直接的想法是保存每一个节点的父节点，需要的时候直接根据下标获取。刚开始用的 int[][] 超出了空间限制，后来改成 List<Integer>[] 虽然多通过了几个测试用例，但是后面会超时。仔细分析最坏的情况下（所有节点仅有一个子树的情况），需要添加 n(n+1)/2 个父节点(首项为1，公差为1的等差数列求和)，时间复杂度是O(n^2)。

一个解决办法是不要保存重复的父节点，以只有一个子树的情况举例，最后一个节点第k个祖先，就是其父节点的第k-1个祖先。如果这个节点已经保存有祖先节点的信息，就无需重复计算了。

所以我的解决方案就是使用缓存，如果父节点的祖先信息没有保存，就将当前节点的祖先信息写入缓存，直到遇到存在缓存的祖先节点，如果它记录的祖先节点个数大于k - cnt就直接返回，否则继续向该缓存的祖先节点集合添加，直到遇到下一个有缓存的节点或者cnt == k。

这种方法虽然能够通过，但是与测试用例的的顺序是有关的，如果是从子节点逐步向前测试的话，缓存一直不命中，时间复杂度还是O(n^2)。

官方的解法使用的是倍增的思想，好像还挺常用的，算是个模板算法。核心思想是保存当前节点的父节点，爷爷节点，爷爷的爷爷节点......，即每个节点 x 的第 2^i 个祖先节点。这样不论k取什么值，都可以分解为不同的2的幂之和，然后向前查找即可。预处理的时间复杂度是O(nlogn)，查询的时间复杂度是O(logk)。

代码

/**
 * @date 2024-04-06 9:45
 */
public class TreeAncestor1483 {

    /**倍增的写法 */
    public static class TreeAncestor_v4 {

        int[][] dp;

        public TreeAncestor_v4(int n, int[] parent) {
            dp = new int[16][];
            dp[0] = parent;
            for (int i = 1; i < 16; i++) {
                dp[i] = new int[n];
                Arrays.fill(dp[i], -1);
            }

            for (int i = 1; i < 16; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[i - 1][j] != -1) {
                        dp[i][j] = dp[i - 1][dp[i - 1][j]];
                    }
                }
            }
        }

        public int getKthAncestor(int node, int k) {
            int p = node;
            int b = 0;
            int mod;
            while (k != 0) {
                mod = k & 1;
                if (mod == 1) {
                    p = dp[b][p];
                    if (p == -1) {
                        return -1;
                    }
                }
                k = k >> 1;
                b++;
            }
            return p;
        }
    }

    int[] parent;
    List<Integer>[] cache;

    public TreeAncestor1483(int n, int[] parent) {
        this.parent = parent;
        cache = new ArrayList[n];
        for (int i = 0; i < cache.length; i++) {
            cache[i] = new ArrayList<>();
        }
    }

    public int getKthAncestor(int node, int k) {
        if (node == -1) {
            return -1;
        }
        int cnt = 0;
        int p = node;
        while (cnt != k && p != -1) {
            if (cache[p].size() == 0) {
                cache[node].add(parent[p]);
                p = parent[p];
                cnt++;
            } else {
                if (cache[p].size() >= k - cnt) {
                    return cache[p].get(k - cnt - 1);
                } else {
                    cnt += cache[p].size();
                    node = p;
                    p = cache[p].get(cache[p].size() - 1);
                }
            }

        }
        return p;
    }
}

性能

这里是使用缓存写法的耗时，官方题解的耗时差不多也是这个样。

使用倍增的写法

目标

给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

请你返回 好 子数组的最大可能 分数 。

示例 1：

输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。

示例 2：

输入：nums = [5,5,4,5,4,1,1,1], k = 0
输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 2 * 10^4
• 0 <= k < nums.length

思路

题目中定义的好子数组必须要包含下标k，且其元素最小值乘以它的长度应最大。相同长度的子数组其最小值通常不同，应取最小值中最大的，这样才能在窗口固定的情况下求得最大分数。

刚开始我把这个问题作为一个动态规划问题来求解：有一个窗口，在下标k的位置有一个固定轴，窗口可以左右滑动，拉伸，但窗口边缘不能越过k。然后求解窗口大小固定时，滑动窗口内最小元素取最大时的状态。接着扩展窗口，新窗口的取值依赖于上一窗口，只需在上一窗口的基础上左右各扩展一个元素进行比较即可。

但是我马上就遇到了问题，因为k的位置是不确定的，窗口左右滑动总会有一边先到达边界，然后怎么处理？上一个窗口取得较大的最小值可能是在k左侧，当窗口到达左侧边界后就无法再移动了，这样势必会有一部分覆盖到k右侧，我们无法再用一侧的最优解来掩盖另一侧了。而右边新加入窗口的元素与上一个状态选择的最小值无法确定新的最小值。因为窗口记录的是左右两侧的最优解，单独某一侧的状态并没有被记录。比如 nums=[10,9,8,7,6,5,3,2,2,4,9,4,11,3,4]，k=5，当窗口大小为6时，左侧的最小值是5，右侧最小值是2（但是我们并没有记录），我们记录的是较大的5。当窗口大小为7时，左侧窗口最小值为3（必须跨过k了），右侧新加入窗口的值是4，如果与上一个状态比较，我们可能会选择4，但是右侧最小值是2，我们应该选3。

于是我想可能需要分别记录左右两侧的状态。我们为什么要记录状态？上面记录状态是为了与新进入窗口的元素比较来选择最优解，我们现在记录左右两侧的什么呢？

随着思考的深入，我觉得应该放弃所谓滑动窗口这个概念了，不应该在左右两侧同时求解。

思考这个问题，窗口增大之后，其中元素的最小值会怎么变？反正最小值一定不会变大。于是只要新加入的元素比窗口内已经选定的最小值大就可以一直扩张，因为最小值没有变化，窗口大小越大分数就越大。当遇到比当前窗口内最小值小的元素时就需要比较窗口另一侧的值，哪边的更大就从哪边扩张。如此反复即可。

代码

/**
 * @date 2024-03-19 0:16
 */
public class MaximumScore {

    public int maximumScore_v2(int[] nums, int k) {
        if (nums.length == 1) {
            return nums[0];
        }
        int res = 0;
        int l = k - 1, r = k + 1;
        int lmin = nums[k], rmin = nums[k];
        while (l >= 0 || r < nums.length) {
            if (l >= 0) {
                lmin = Math.min(lmin, nums[l]);
            }
            if (r < nums.length) {
                rmin = Math.min(rmin, nums[r]);
            }
            if ((lmin >= rmin && l >= 0) || r >= nums.length) {
                l--;
                while (l >= 0 && lmin <= nums[l]) {
                    l--;
                }
                // r-l是窗口大小（不包括r），由于l多减了1，所以这里要减去
                res = Math.max(res, lmin * (r - l - 1));
            } else {
                r++;
                while (r < nums.length && rmin <= nums[r]) {
                    r++;
                }
                // r-l是窗口大小（不包括l）由于r多加了1，所以这里要减去
                res = Math.max(res, rmin * (r - l - 1));
            }
        }
        return res;
    }
}

性能

目标

给你一棵 n 个节点的无向树，节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 在树中有一条边。

请你返回树中的 合法路径数目 。

如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数，那么我们称路径 (a, b) 是 合法的 。

注意：

• 路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列，序列中的节点 互不相同 ，且相邻节点之间在树上有一条边。
• 路径 (a, b) 和路径 (b, a) 视为 同一条 路径，且只计入答案 一次 。

思路

质数是指在大于1的自然数（非负整数）中，除了1和它本身以外不再有其他因数的自然数。

现在有一颗 n 个节点的无向树，要求任意两个连通节点间恰好有一个质数节点的路径数。树是一种无环连通图，问题可以转化为从树中选取两个节点，节点之间的路径只经过一个质数节点。由于没有环，所以两点之间的路径是唯一的。

1. 两个都是质数节点要排除掉。
2. 以质数节点为中心，与它邻接的非质数节点符合条件。即以质数节点为中心加上与之相连的非质数节点任取两个均可。我们可以称直接与质数节点相连的非质数节点为直接节点。
3. 直接节点连通的非质数节点也可能满足条件，需要要减去直接节点向外连通的路径，即直接节点加上其向外连通的节点之间任取两个的路径数。

按照上面的思路，先要找到所有的质数节点，涉及到质数判断。同时保存与之直接相连的非质数节点。然后保存非质数节点的边，使用Map保存，边的两个端点都保存进去，方便后续向外查找连通的节点。

得到满足条件的节点总数，根据排列组合公式C(n,2) = n!/(2!(n-2)!) = (n-1)n/2 求得路径总数D。

将外围节点k向外连通节点总数记为Ik，无效路径数为(Ik-1)Ik/2。

最终的结果就是D - Σ(Ik-1)Ik/2

代码

/**
 * @date 2024-02-27 0:22
 */
public class CountPaths {

    public Map<Integer, Set<Integer>> primeEdges = new HashMap<>();
    public Map<Integer, Set<Integer>> notPrimeEdges = new HashMap<>();
    public Map<Integer, Integer> indirectNodesNumMap = new HashMap<>();
    Set<Integer> counter = new HashSet<>();

    public long countPaths(int n, int[][] edges) {
        for (int i = 0; i < n - 1; i++) {
            int[] edge = edges[i];
            boolean i0 = isPrimeNumber(edge[0]);
            boolean i1 = isPrimeNumber(edge[1]);
            if (i0 && !i1) {
                primeEdges.computeIfAbsent(edge[0], k -> new HashSet<>());
                primeEdges.get(edge[0]).add(edge[1]);
            } else if (!i0 && i1) {
                primeEdges.computeIfAbsent(edge[1], k -> new HashSet<>());
                primeEdges.get(edge[1]).add(edge[0]);
            } else if(!i0){
                notPrimeEdges.computeIfAbsent(edge[0], k -> new HashSet<>());
                notPrimeEdges.computeIfAbsent(edge[1], k -> new HashSet<>());
                notPrimeEdges.get(edge[0]).add(edge[1]);
                notPrimeEdges.get(edge[1]).add(edge[0]);
            }
        }
        long res = 0;
        for (Integer primeNode : primeEdges.keySet()) {
            Set<Integer> nonPrimeNodesOfPrimeEdge = primeEdges.get(primeNode);
            counter.clear();
            int total = 0;
            for (int nonPrimeNode : nonPrimeNodesOfPrimeEdge) {
                counter.add(nonPrimeNode);
                if (indirectNodesNumMap.get(nonPrimeNode) == null) {
                    indirectNodesNumMap.put(nonPrimeNode, 1);
                    countEdges(nonPrimeNode, nonPrimeNode);
                }
                total += indirectNodesNumMap.get(nonPrimeNode);
            }
            total = total + 1;
            res += total * (total - 1L) / 2L;
            for (int nonPrimeNode : nonPrimeNodesOfPrimeEdge) {
                int indirectNodesNum = indirectNodesNumMap.get(nonPrimeNode);
                res -= indirectNodesNum * (indirectNodesNum - 1L) / 2L;
            }
        }
        return res;
    }

    public Set<Integer> countEdges(int key, int nonPrimeNode) {
        if (notPrimeEdges.get(nonPrimeNode) != null) {
            for (Integer node : notPrimeEdges.get(nonPrimeNode)) {
                if (!counter.contains(node)) {
                    indirectNodesNumMap.put(key, indirectNodesNumMap.get(key) + 1);
                    counter.add(node);
                    countEdges(key, node);
                }
            }
        }
        return counter;
    }

    public boolean isPrimeNumber(int num) {
        if (num == 1) {
            return false;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return false;
        }
        for (int i = 3;  i * i <= num; i+=2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
//        int[][] edges = new int[][]{new int[]{1, 2}, new int[]{1, 3}, new int[]{2, 4}, new int[]{2, 5}};
        int[][] edges = new int[][]{new int[]{1, 2}, new int[]{4, 1}, new int[]{3, 4}};
        CountPaths main = new CountPaths();
//        System.out.println(main.countPaths(5, edges));
        System.out.println(main.countPaths(4, edges));
    }
}

性能

勉强通过。有时间再回来看看题解吧。

目标

小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器，计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。

主办方请小扣回答出一个长度为 N 的数组，第 i 个元素(0 <= i < N)表示将 0~i 号计数器 初始 所示数字操作成满足所有条件 nums[a]+1 == nums[a+1],(0 <= a < i) 的最小操作数。回答正确方可进入秋日市集。

由于答案可能很大，请将每个最小操作数对 1,000,000,007 取余。

思路

老实说这道题我花了好一会儿才弄清楚题目要求，最后解法还因为超时没有通过。

先解释一下目标吧，实际上需要求解的是每一个位置上的局部最优解。所谓局部指仅考虑当前位置及之前的所有位置的操作次数。所谓最优是指初始序列达到满足条件的状态（公差为1的等差数列）时所做操作总和的最小值。如果有N个计数器，那么就有N个满足条件的序列，有可能前面操作最少的序列并不是后面操作最少的序列，即前面位置的总操作次数可能并不是当前最优解的一部分。可以参考上面图片的示例3。

我的思路就是直接暴力破解，循环遍历输入的数组，在第i次遍历中，分别将（0 ~ i-1）位置上的元素作为基点k，左侧的序列依次减1，右侧的依次加1。在第k个序列中求解（0 ~ i-1）位置上操作次数的累加和。在第j个位置上的操作次数为 nums[k]-(k-j)。

代码

public static int[] numsGame2(int[] nums) {
    int[] res = new int[nums.length];
    // 累加k序列的操作总和
    int[] acc = new int[nums.length];
    for (int i = 1; i < nums.length; i++) {
        for (int k = 0; k <= i; k++) {
            int temp = acc[k];
            // 增加一些判断跳过一些计算
            if(temp >= res[i] && res[i] != 0){
                continue;
            }
            // 这里看似套了3个循环，但其实只有在k序列第一次出现时才会循环i次，那么前面的i-1次只需从acc中累计即可，实际时间复杂度是O(n^2)
            for (int j = temp == 0 ? 0 : i; j <= i; j++) {
                temp += Math.abs(nums[j] - (nums[k] - (k - j)));
            }
            acc[k] = temp;
            if (k == 0) {
                res[i] = temp;
            } else {
                res[i] = Math.min(res[i], temp);
            }
        }
        res[i] = res[i] % 1000000007;
    }
    return res;
}

如上表所示，如果序列是[a,b,c,d]，基点k等于c的时候，前2次从acc累加，最后一次需要重新累加。时间复杂度为O(n^2)。这和我们常见的外层循环N次，内层循环N次不同。循环的计算次数序列为1、3、5、7...，根据等差数列求和公式：Sn = n × a1 + (n × (n-1)/2) × d，当 d=2，a1=1 时，Sn = n^2。

性能

由于题目给出的数组最大长度是10^5，暴力求解是不可行的。也尝试了增加条件判断跳过一些计算但还是无法降低问题的规模。于是就开始怀疑是否前面的计算结果是否与后面的计算有关联，可以简化后面的计算？更优的算法复杂度应为O(nlogn)、O(logn) 和 O(n)。我思考了很久，应该是存在知识盲区了。我去看了答案，涉及到求中位数。其实一开始有想过中位数，方差均值这些，但是没想到和这个最优解有什么关系。今天没时间了，抽空再看看吧。