shelterofly

目标

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

说明：

• 1 <= n <= 2 * 10^4
• edges.length == n - 1
• 0 <= ai, bi < n
• ai != bi
• 所有 (ai, bi) 互不相同
• 给定的输入 保证 是一棵树，并且 不会有重复的边

思路

一看到这个题目就想起了换根动态规划，参考2581_统计可能的树根数目。

这个题是medium，但是感觉比上面参考那个hard题难多了，状态转换方程很难想。基本都是靠错误案例调试出来的。最开始写的dp方法调试了好几个小时，测试通过但是超时。然后开始怀疑dp根本就没法解，因为换根后状态是变化的，需要动态调整高度，并且还要区分当前节点是否为原来的根提供了最大高度。结果改到最后和暴力解法差不多了。

这种解法的关键是弄清楚换根之后节点高度的变化。经过分析只有换根的两个节点受到影响。分为两种情况，如果新根为旧根提供了最大高度，那么旧根应变为其邻接节点次大高度+1（第一次递归进来时计算）。如果新根没有为旧根提供最大高度，旧根高度不变仍为其邻接节点最大高度+1（第一次递归进来时计算）。新根是其邻接节点最大高度+1（这里面包括了刚才改变高度的旧根）。

注意：这里每个节点记录的是以0为根进行dfs，从叶子节点累加的高度。因此，当前节点高度就等于邻接节点最大高度加1。

代码

/**
 * @date 2024-03-17 16:04
 */
public class FindMinHeightTrees {

    public int[] res;
    public int minHeight;
    List<Integer>[] g;
    int[] dp;

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        g = new ArrayList[n];
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
        }
        dp = new int[n];
        res = new int[n];
        minHeight = n;
        for (int i = 0; i < edges.length; i++) {
            g[edges[i][0]].add(edges[i][1]);
            g[edges[i][1]].add(edges[i][0]);
        }
        dfs(0, 0);
        redfs(0, 0);

        List<Integer> minHeights = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (res[i] == minHeight) {
                minHeights.add(i);
            }
        }
        return minHeights;

    }

    public void redfs(int root, int parent) {
        // 进入到该层后，保存其最大与次大深度，后面换根后再回来遍历其它兄弟节点时不会受到换根影响
        // 由于是深度遍历，换根到子节点与当前根的深度有关
        // 由子节点返回后，状态已保存，不受换根影响
        int max = 0;
        int second = 0;
        for (Integer neighbor : g[root]) {
            if (dp[neighbor] > max) {
                second = max;
                max = dp[neighbor];
            } else if (dp[neighbor] > second) {
                second = dp[neighbor];
            }
        }
        // max是与root相邻节点的高度，加1才是root的最大高度
        res[root] = max + 1;
        // 更新最小高度
        minHeight = Math.min(minHeight, res[root]);
        for (Integer next : g[root]) {
            if (next == parent) {
                // 遇到叶子节点返回
                continue;
            }
            // 换到下一个根next，修改root的高度，如果下一个点为当前点提供了最大高度，那么当前节点高度为
            // 次高加一，否则是最高加一
            dp[root] = (dp[next] == max ? second : max) + 1;
            redfs(next, root);
        }
    }

    public int dfs(int root, int parent) {
        dp[root] = 1;
        for (Integer next : g[root]) {
            if (next != parent) {
                dp[root] = Math.max(dp[root], dfs(next, root) + 1);
            }
        }
        return dp[root];
    }

    public static void main(String[] args) {
        FindMinHeightTrees main = new FindMinHeightTrees();
//        System.out.println(main.findMinHeightTrees(4, new int[][]{{1, 0}, {1, 2}, {1, 3}}));
//        System.out.println(main.findMinHeightTrees(6, new int[][]{{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}}));
//        System.out.println(main.findMinHeightTrees(7, new int[][]{{0, 1}, {1, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 6}}));
//        System.out.println(main.findMinHeightTrees(8, new int[][]{{0,1},{1,2},{2,3},{0,4},{4,5},{4,6},{6,7}}));
        System.out.println(main.findMinHeightTrees(11, new int[][]{{0, 1}, {0, 2}, {2, 3}, {0, 4}, {2, 5}, {5, 6}, {3, 7}, {6, 8}, {8, 9}, {9, 10}}));
//        System.out.println(main.findMinHeightTrees(2, new int[][]{{0, 1}}));
    }
}

性能

目标

给你一个下标从 0 开始、由正整数组成的数组 nums 。

你可以在数组上执行下述操作 任意 次：

• 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

示例 1：

输入：nums = [2,3,7,9,3]
输出：21
解释：我们可以在数组上执行下述操作：
- 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
- 选中 i = 1 ，得到数组 nums = [5,16,3] 。
- 选中 i = 0 ，得到数组 nums = [21,3] 。
最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2：

输入：nums = [5,3,3]
输出：11
解释：我们可以在数组上执行下述操作：
- 选中 i = 1 ，得到数组 nums = [5,6] 。
- 选中 i = 0 ，得到数组 nums = [11] 。
最终数组中只有一个元素，即 11 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

思路

这个题要我们对一个数组进行操作并返回最大的元素值。这里的操作指的是合并相邻的非严格递增元素。

刚开始没有头绪，如果真的按照操作步骤先把符合条件的值求出来，替换掉较大元素的值并删掉较小元素，那么就需要频繁地移动数组数据。

除此之外需要考虑一个重要的问题，如何合并才能使最终的结果最大？如果从前向后合并，比如 [2,6,7] 先合并前两个得到[8,7]肯定没有从后向前合并得到的值 [2, 13] [15] 大。是否存在那种先从前向后合并，然后再从后向前合并才能得到最大值的情况？

刚开始是不那么容易弄清的。也考虑过优先合并 后面的元素值 比 合并后的元素值 大的 元素，提前考虑了一步能否避免上面的情况？好像可以，因为操作没有破坏原数组能否合并的状态。那么这种操作需要循环几次？时间复杂度是O(n)~O(nlogn)吗？

[1,2,1,4,1,2,1,4]一次遍历后可以变为[3,5,3,5]，然后再遍历一次得到 [8, 8]，再来一次 [16]，即O(nlogn)。更好的情况就是递增序列O(n)。

经过上面的分析可以发现，优先使后面的元素最大才能得到最大值。那么为什么不从后向前遍历并累加呢？如果遇到一个元素的值比后面所有元素的累加和还要大，那不管前面怎么操作，由于元素都是正整数，合并后只会更大。

想清楚了这一点就非常简单了。

代码

/**
 * @date 2024-03-14 11:29
 */
public class MaxArrayValue {

    public long maxArrayValue(int[] nums) {
        long res = nums[nums.length - 1];
        for (int i = nums.length - 1; i >= 1; i--) {
            res = res >= nums[i - 1] ? res + nums[i - 1] : nums[i - 1];
        }
        return res;
    }

    public static void main(String[] args) {
        MaxArrayValue main = new MaxArrayValue();
//        int[] nums = new int[]{2, 3, 7, 9, 3};
//        int[] nums = new int[]{5, 3, 3};
//        int[] nums = new int[]{77};
        int[] nums = new int[]{34, 95, 50, 12, 25, 100, 21, 3, 25, 16, 76, 73, 93, 46, 18};
        System.out.println(main.maxArrayValue(nums));
    }
}

性能

目标

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。

示例 1：

输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。

示例 2：

输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

说明：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 10^5
• 1 <= grid[i][j] <= 10^6

思路

题目要我们求从矩阵第一列出发的最大移动次数。当前单元格可以移动到其后面一列的上中下三格，如果相应位置的值大于当前元素的话。

这道题可以使用动态规划来做，虽然重叠的子问题不多。从右向左，从下到上/从上到下，计算每个单元格可以移动的最大次数。然后求第一列的最大值即可。

值得注意的是这种列在外层从右向左的循环方式。如果像平时那样外层行循环内层列循环，那么写状态转移方程时，子问题可能还未计算。

官网题解给的是广度优先搜索的方法，遍历第一列起点，将能到达的第二列的格子加入集合，然后遍历这些格子，如此反复直到无法继续或者到达矩阵最大边界n-1。

代码

/**
 * @date 2024-03-16 15:08
 */
public class MaxMoves {

    public int maxMoves(int[][] grid) {
        int[][] dp = new int[grid.length][];
        for (int i = 0; i < grid.length; i++) {
            dp[i] = new int[grid[i].length];
        }
        int res = 0;
        int i = grid.length - 1;
        for (int j = grid[i].length - 2; j >= 0; j--) {
            i = grid.length - 1;
            for (; i >= 0; i--) {
                if (i != 0 && grid[i][j] < grid[i - 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + 1] + 1);
                }
                if (grid[i][j] < grid[i][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j + 1] + 1);
                }
                if (i != grid.length - 1 && grid[i][j] < grid[i + 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j + 1] + 1);
                }
                if (j == 0){
                    res = Math.max(res, dp[i][0]);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        MaxMoves main = new MaxMoves();
        System.out.println(main.maxMoves(new int[][]{{2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}}));
    }
}

性能

网友的题解还有网格DFS（2ms）、BFS（6ms）。虽然时间复杂度都是O(mn)，但是性能差别还是挺大的。有时间可以分析一下，性能到底差在哪里。先不追求性能100%了，先以最快的速度将题过一遍。

目标

给出一个满足下述规则的二叉树：

1. root.val == 0
2. 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
3. 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

• FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
• bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

说明：

• TreeNode.val == -1
• 二叉树的高度不超过 20
• 节点的总数在 [1, 10^4] 之间
• 调用 find() 的总次数在 [1, 10^4] 之间
• 0 <= target <= 10^6

思路

dfs还原节点val，并将其加入到Hash表中，直接contains判断。

这个题被标为medium，估计是想让我们自己实现Hash表来查找元素吧。

代码

/**
 * @date 2024-03-12 2:41
 */
public class FindElements {
    Set<Integer> elements;

    public FindElements(TreeNode root) {
        elements = new HashSet<>();
        recover(root, 0);
    }

    public void recover(TreeNode root, int value) {
        if (root == null) {
            return;
        }
        root.val = value;
        elements.add(value);
        recover(root.left, 2 * value + 1);
        recover(root.right, 2 * value + 2);
    }

    public boolean find(int target) {
        return elements.contains(target);
    }
}

性能