标签： 动态规划

2028.找出缺失的观测数据

目标

现有一份 n + m 次投掷单个 六面 骰子的观测数据，骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份，你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的 平均值 。

给你一个长度为 m 的整数数组 rolls ，其中 rolls[i] 是第 i 次观测的值。同时给你两个整数 mean 和 n 。

返回一个长度为 n 的数组，包含所有缺失的观测数据，且满足这 n + m 次投掷的 平均值 是 mean 。如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。

k 个数字的 平均值 为这些数字求和后再除以 k 。

注意 mean 是一个整数，所以 n + m 次投掷的总和需要被 n + m 整除。

示例 1：

输入：rolls = [3,2,4,3], mean = 4, n = 2
输出：[6,6]
解释：所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。

示例 2：

输入：rolls = [1,5,6], mean = 3, n = 4
输出：[2,3,2,2]
解释：所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。

示例 3：

输入：rolls = [1,2,3,4], mean = 6, n = 4
输出：[]
解释：无论丢失的 4 次数据是什么，平均值都不可能是 6 。

示例 4：

输入：rolls = [1], mean = 3, n = 1
输出：[5]
解释：所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。

说明：

  • m == rolls.length
  • 1 <= n, m <= 10^5
  • 1 <= rolls[i], mean <= 6

思路

已知 m+n 个投骰子的观测数据的均值 mean，以及其中 m 个观察数据 rolls，返回缺失的观测数据，如果存在多个只返回其中一组，如果不存在答案返回空数组。

我们可以很容易计算出观测数据的总和 mean * (m + n)，用它减去已知的观测数据和 sum，得到 diff。

  • 如果 diff > n * 6 说明 剩余的 n 次都得到 6 点也不够，返回空数组。
  • 如果 diff < n 说明 剩余的 n 次都得到 1 点也多余，返回空数组。
  • 否则，问题变成选 n 个数字使其和等于 diff，每个数的取值范围是 1 ~ 6。

这让我想起了背包问题还有之前做过的硬币找零，组合总和等问题。这里只需要返回一种可能就行了，不需要动态规划。

可以先计算 val = diff / n，如果有剩余 r，就为 r 个值加1。

代码

/**
 * @date 2024-05-27 9:20
 */
public class MissingRolls2028 {

    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length;
        int sum = 0;
        for (int roll : rolls) {
            sum += roll;
        }
        int diff = mean * (m + n) - sum;
        if (diff > n * 6 || diff < n) {
            return new int[0];
        }
        int[] res = new int[n];
        int val = diff / n;
        diff = diff - val * n;
        Arrays.fill(res, val);
        for (int i = 0; i < diff; i++) {
            res[i]++;
        }
        return res;
    }
}

性能

2079.给植物浇水

目标

你打算用一个水罐给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。x = -1 处有一条河，你可以在那里重新灌满你的水罐。

每一株植物都需要浇特定量的水。你将会按下面描述的方式完成浇水：

  • 按从左到右的顺序给植物浇水。
  • 在给当前植物浇完水之后，如果你没有足够的水 完全 浇灌下一株植物，那么你就需要返回河边重新装满水罐。
  • 你 不能 提前重新灌满水罐。

最初，你在河边（也就是，x = -1），在 x 轴上每移动 一个单位 都需要 一步 。

给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有一个整数 capacity 表示水罐的容量，返回浇灌所有植物需要的 步数 。

示例 1：

输入：plants = [2,2,3,3], capacity = 5
输出：14
解释：从河边开始，此时水罐是装满的：
- 走到植物 0 (1 步) ，浇水。水罐中还有 3 单位的水。
- 走到植物 1 (1 步) ，浇水。水罐中还有 1 单位的水。
- 由于不能完全浇灌植物 2 ，回到河边取水 (2 步)。
- 走到植物 2 (3 步) ，浇水。水罐中还有 2 单位的水。
- 由于不能完全浇灌植物 3 ，回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。
需要的步数是 = 1 + 1 + 2 + 3 + 3 + 4 = 14 。

示例 2：

输入：plants = [1,1,1,4,2,3], capacity = 4
输出：30
解释：从河边开始，此时水罐是装满的：
- 走到植物 0，1，2 (3 步) ，浇水。回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。回到河边取水 (4 步)。
- 走到植物 4 (5 步) ，浇水。回到河边取水 (5 步)。
- 走到植物 5 (6 步) ，浇水。
需要的步数是 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30 。

示例 3：

输入：plants = [7,7,7,7,7,7,7], capacity = 8
输出：49
解释：每次浇水都需要重新灌满水罐。
需要的步数是 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49 。

说明：

  • n == plants.length
  • 1 <= n <= 1000
  • 1 <= plants[i] <= 10^6
  • max(plants[i]) <= capacity <= 10^9

思路

简单的动态规划。

代码

/**
 * @date 2024-05-08 0:01
 */
public class WateringPlants2079 {
    public int wateringPlants(int[] plants, int capacity) {
        int n = plants.length;
        int[] dp = new int[n];
        int remainder = capacity - plants[0];
        dp[0] = 1;
        for (int i = 1; i < plants.length; i++) {
            if (remainder >= plants[i]) {
                remainder -= plants[i];
                dp[i] = dp[i - 1] + 1;
            } else {
                remainder = capacity - plants[i];
                dp[i] = dp[i - 1] + (i << 1) + 1;
            }
        }
        return dp[n - 1];
    }
}

性能

377.组合总和 Ⅳ

目标

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。请注意，顺序不同的序列被视作不同的组合。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

示例 2：

输入：nums = [9], target = 3
输出：0

说明：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

思路

这个题要求满足条件的排列数，从给定数组中选择任意数字，同一数字可以重复选择，使所选序列的和等于target。

类似于70.爬楼梯、322.零钱兑换

首先初始化给定数组的dp，然后遍历0~target，计算dp。

代码

/**
 * @date 2024-04-22 8:31
 */
public class CombinationSum377 {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int[] dp = new int[target + 1];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= target) {
                dp[nums[i]] = 1;
            }
        }
        for (int i = 0; i <= target; i++) {
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}

性能

39.组合总和

目标

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

思路

一看到这道题就想到要用动态规划，但是昨天看了回溯算法的视频，所以就试图使用dfs去写。

先从target开始，循环减去可选数字，然后递归。想法是好的，但是这种集合嵌套集合的操作一会就把我搞晕了，向下传递什么，返回什么？有机会再想想吧。

还是用动态规划吧，难点在于去重。刚开始甚至写了hash函数，但是它不能处理2, 5（2 3） 与 4（2 2）, 3的情况，dp[2] + dp[5] 与 dp[4] + dp[3] 得到的组合是相同的 [2, 2, 3]。

这让我想到了518.零钱兑换II，这两道题本质是一样的。那个只让返回组合数，这个需要返回具体的组合。

去重的精髓就在于不能提前初始化dp，只能在第一次访问到候选值的时候初始化。

代码

/**
 * @date 2024-04-20 10:20
 */
public class CombinationSum39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>>[] dp = new List[target + 1];
        for (int i = 0; i <= target; i++) {
            dp[i] = new ArrayList<>();
        }
        for (int candidate : candidates) {
            if (candidate <= target) {
                List<Integer> list = new ArrayList<>();
                list.add(candidate);
                dp[candidate].add(list);
            }
            for (int i = candidate; i <= target; i++) {
                for (List<Integer> lj : dp[i - candidate]) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(candidate);
                    tmp.addAll(lj);
                    dp[i].add(tmp);
                }
            }
        }
        return dp[target];
    }
}

性能

1483.树节点的第K个祖先

目标

给你一棵树，树上有 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;
    }
}

性能

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

使用倍增的写法

1997.访问完所有房间的第一天

目标

你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。

最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：

  • 假设某一天，你访问 i 号房间。
  • 如果算上本次访问，访问 i 号房间的次数为 奇数 ，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
  • 如果算上本次访问，访问 i 号房间的次数为 偶数 ，那么 第二天 需要访问 (i + 1) mod n 号房间。

请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 10^9 + 7 取余后的结果。

示例 1：

输入：nextVisit = [0,0]
输出：2
解释：
- 第 0 天，你访问房间 0 。访问 0 号房间的总次数为 1 ，次数为奇数。
  下一天你需要访问房间的编号是 nextVisit[0] = 0
- 第 1 天，你访问房间 0 。访问 0 号房间的总次数为 2 ，次数为偶数。
  下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1
- 第 2 天，你访问房间 1 。这是你第一次完成访问所有房间的那天。

示例 2：

输入：nextVisit = [0,0,2]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,0,0,1,2,...] 。
第 6 天是你访问完所有房间的第一天。

示例 3：

输入：nextVisit = [0,1,2,0]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,1,2,2,3,...] 。
第 6 天是你访问完所有房间的第一天。

说明：

  • n == nextVisit.length
  • 2 <= n <= 10^5
  • 0 <= nextVisit[i] <= i

思路

这道题用了3.5小时，也不知道花费这么多精力到底值不值得。这道题基本上是调试出来的，好多坑都没有考虑到。

说回这道题，有 0 到 n-1 共 n 个房间，每天可以访问一个房间，第 0 天访问 0 号房，然后根据当前房间的被访问次数来决定明天访问的房间。通俗来讲就是，如果当前房间cur被访问次数为奇数，访问包括当前房间在内的由参数指定的房间[0, cur]；如果为偶数，则访问编号为cur+1的房间。需要我们返回首次访问 n-1 房间是第几天。

我上来想都没想就直接按照题意把代码写出来了，主要是理解题意。不出所料，提交超时。

在第30个用例的时候超时了，参数是这样的 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]，即每前进一个房间都退回到第0个房间从头开始。总共 74 个房间，由于每个房间需要访问偶数次才可以前进，因此 f(n) = 2(f(n-1) + 1) 其中 f(0)=0, f(1)=2，n为正整数。两边都加上2得f(n) + 2 = 2(f(n-1) + 2)，根据等比数列公式an = a1*q^(n-1)，代入a1 = f(1) + 2 = 4, q = 2，得 f(n) = 2^(n+1) - 2。访问到编号为 74-1 的房间要等到第 2^74 -2 天。计算这个主要是为了说明问题的规模，按照题目描述去循环肯定是不行的。

很明显我们需要使用动态规划来求解。那么状态转移方程如何写？哪些子问题是重复计算的？经过观察我们知道，首次访问到某一房间的时候，之前所有房间的访问次数一定是偶数。当我们根据参数向后返回的时候，相当于是从指定的房间到当前房间又重新经历了一遍，因为参数指定的房间是固定的。于是我们可以保存首次访问到某房间是第几天，当后退到某房间之后就不用再重新循环了，直接计算天数，即天数累加上 dp[max] - dp[back] + 1。

上面的算法是题目完成之后才弄明白的，写代码的时候遇到了许多坑：

  1. 首先是初值问题，dp[0]到底取1还是0。刚开始没有想明白dp[n]的含义，根据上面的定义，第一次访问到0号房间是第0天，应该取0。但是程序里需要在第一次访问到房间的时候，天数加1然后赋值给dp，但是对于第0个房间，会错误地将dp[0]改为1，那么后续的天数计算就需要多加1，因为少减了1天（这个问题可以将初始的maxRoom置为0，可以回避该分支的执行）。刚开始我根据错误的初始条件，观察上面超时的用例写的状态转移方程为dp[max] - dp[back] + 2，提交之后发现有的测试用例给出的结果比预期结果多了1，排查了半天才发现问题。

  2. 日期编号溢出的问题，刚开始dp与day都使用的int类型，在计算状态转移方程的时候有可能溢出，修改为long之后能够通过一些测试用例，但是后面还是会出现负值。这时我开始注意到这个问题了，就是dp保存的是取模之后的值，相减的时候会不会有问题？我们不可能无限制地扩展bit位，不可能存储准确的数值，取模是必要的。但是结果为什么还是有负值？这时灵光一闪，发现返回的负值只要加上MOD就可以得到正确的结果。这一定不是偶然的，后来才明白是因为后面的天数取模变小了，相减出现了负值，并不是溢出。但是，即便是负值一直取模，到最后返回结果的时候再加MOD也是正确的（看了官方题解，是在相减的时候加上了MOD）。

    注意以下事实：

    在java中进行取模运算时，结果的符号与被除数（即左边的操作数）相同：

    • -7 % 15 = -7
    • 7 % -15 = 7
    • -7 % -15 = -7
    • -7 % 3 = -1
    • 7 % -3 = 1
    • -7 % -3 = -1
    • (-7 + 15) % 15 = -7 + 15

    补码（Two's Complement）是有符号数的一种二进制表示方式，主要用于计算机系统中数值的表示和存储。这种表示方式具有统一处理符号位和数值位、统一处理加法和减法的优点。

    补码命名中的“2的补数”描述了补码的一个特性：一个补码可以通过被2的位长次方减去，得到它的相反数。例如，对于一个4位的补码，0001（十进制为1）的相反数可以通过计算2^4 - 0001得到，结果为1111（十进制为-1）。

    在计算机中，正数的补码与其原码相同，而负数的补码则是通过对其绝对值的原码取反后加1得到。这种转换过程与原码的转换过程几乎相同，不需要额外的硬件电路。

    补码的使用在电路设计上相当方便，因为只要有加法电路及补码电路，就可以完成各种有号数的加法和减法运算。

    对一个正数取反加1，可以得到其相反数的补码。

    对一个负数取反加1，可以得到其绝对值。因为负数a的补码就是2^n - |a|。 其中2^n 可以想象成 n 个bit位均为1的二进制数加1。用所有bit位为1的数去减任意数就是取反，因为肯定是1变0，0变1。最后再加上多出来的1，就得到了补码。

    对n位2进制数（不考虑符号位）求补码其实就是求相对于2^n的补数。

  3. 循环的结束条件问题，最开始使用的结束条件 dp[roomNums - 1] == 0，判断是否是第一次访问使用的是dp[maxRoom] == 0。这就有问题了，第 233/239 个测试用例很特殊，因为结束时的天数刚好等于MOD，取模后为0，导致程序无法结束。于是后面改成了根据访问次数是否为0来判断。但是条件修改之后，访问次数在哪里累加也成了关键，如果在判断之前加就不对，牵一发而动全身。

代码

/**
 * @date 2024-03-28 0:02
 */
public class FirstDayBeenInAllRooms1997 {

    private static final int MOD = 1000000007;

    public int firstDayBeenInAllRooms_v1(int[] nextVisit) {
        int roomNums = nextVisit.length;
        int[] visitCount = new int[roomNums];
        long[] dp = new long[roomNums];
        dp[0] = 0;
        long day = 0;
        int currentRoom = 0;
        int maxRoom = 0;
        visitCount[currentRoom] = 1;
        while (visitCount[roomNums - 1] == 0) {
            if (visitCount[currentRoom] % 2 == 1) {
                currentRoom = nextVisit[currentRoom];
            } else {
                currentRoom = (currentRoom + 1) % roomNums;
                maxRoom = Math.max(currentRoom, maxRoom);
            }
            if (visitCount[maxRoom] == 0) {
                visitCount[currentRoom] += 1;
                day = (day + 1) % MOD;
                    dp[currentRoom] = day;
            } else {
                if (currentRoom != maxRoom) {
                    day = (day + dp[maxRoom] - dp[currentRoom] + 1L) % MOD;
                    currentRoom = maxRoom;
                } else {
                    day = (day + 1) % MOD;
                }
                visitCount[currentRoom]++;
            }
        }
        return (int) (day < 0 ? MOD + day : day);
    }

    public static void main(String[] args) {
        FirstDayBeenInAllRooms1997 main = new FirstDayBeenInAllRooms1997();
        System.out.println(main.firstDayBeenInAllRooms_v1(new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}));
        System.out.println(FastPowerMod.fastPowerMod(2, 74, MOD));
//        System.out.println(main.firstDayBeenInAllRooms_v1(new int[]{0,1,2,0}));
//        System.out.println(main.firstDayBeenInAllRooms_v1(new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 1, 8}));
//        System.out.println(main.firstDayBeenInAllRooms_v1(new int[]{0, 0, 1, 2, 4, 0, 1, 6, 0, 0, 2, 3, 4, 3, 4, 11, 6, 0, 16, 14, 20, 16, 9, 9, 1, 8, 8, 4, 14, 13, 5, 12, 8, 18, 27, 34, 36, 13, 10, 35, 13, 31, 13, 29, 2, 45, 17, 30, 10, 18, 41, 14, 41, 22, 2, 4, 1, 15, 27, 35, 12, 10, 46, 25, 61, 8, 65, 57, 48, 61, 8, 35, 2, 66, 47, 5, 54, 76, 73, 51, 13, 64, 15, 2}));
//        System.out.println(main.firstDayBeenInAllRooms_v1(new int[]{0,0,0,0,2,2,1,2,3,8,9,5,1,6,8,5,10,5,18,2,15,7,22,4,6,10,19,16,3,25,12,28,1,27,25,25,35,16,7,23,37,8,28,8,18,41,36,29}));

    }

性能

518.零钱兑换II

目标

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

说明：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

思路

// todo

代码

/**
 * @date 2024-03-25 8:31
 */
public class CoinChange {

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        CoinChange main = new CoinChange();
//        int amount = 5;
        int amount = 500;
        int[] coins = new int[]{1, 2, 5};
//        System.out.println(main.change(amount, coins));
//        System.out.println(main.change(amount, coins));
        System.out.println(main.change(amount, coins));
    }
}

性能

// todo

322.零钱兑换

目标

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

说明：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

思路

// todo

思考的方向错了，试图用贪心算法枚举可能的组合。做法是优先选面值最大的，取得余数，再计算下一个面值的余数，直到余数为0。但是这样得到的不一定是最优解。尝试将最大面值的个数减一，然后余数加上最大面值，重新计算。但是还是一样的，如果要调整的话，所有面值的个数都要调整，不能只调整最大的，后面的还用贪心，这样问题就不可解了。

代码

/**
 * @date 2024-03-24 0:04
 */
public class CoinChange {

    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        CoinChange main = new CoinChange();
//        int[] coins = new int[]{3, 7};
        int[] coins = new int[]{186, 419, 83, 408};
//        System.out.println(main.coinChange(coins, 9));
        System.out.println(main.coinChange(coins, 6249));
    }
}

性能

// todo

310.最小高度树

目标

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

给你一棵包含 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}}));
    }
}

性能

2684.矩阵中移动的最大次数

目标

给你一个下标从 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%了，先以最快的速度将题过一遍。