标签： 动态规划

494.目标和

目标

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

说明：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

思路

有一个数组，可以在数组元素前加上正负号来组成表达式，问表达式等于target的数目。

如果当前元素为正则累加，否则相减，递归直到所有元素都已列入表达式，如果累加结果等于target则返回1，否则返回0。

//todo 改为递推，或记忆化搜索

代码

/**
 * @date 2024-06-30 20:07
 */
public class FindTargetSumWays494 {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, 1, nums[0], target) + dfs(nums, 1, -nums[0], target);
    }

    public int dfs(int[] nums, int i, int res, int target) {
        if (i == nums.length) {
            return res - target == 0 ? 1 : 0;
        }
        return dfs(nums, i + 1, res + nums[i], target) + dfs(nums, i + 1, res - nums[i], target);
    }

}

性能

139.单词拆分

目标

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

说明：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同

思路

已知一个字符串列表 wordDict 和一个字符串 s，问能否用列表中的元素拼成该字符串，列表中的元素可以重复使用。

很明显需要使用动态规划来求解，假设当前列表元素 word 的长度为 l，子字符串 sub 的长度为 i，如果 sub.substring(0, i-l) 能由字典中的词拼成并且 word.equals(sub.substring(i-l, l)) 那么 sub 也能由字典中的词拼成。

代码

/**
 * @date 2024-06-23 19:58
 */
public class WordBreak139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int length = word.length();
                if (length <= i && dp[i - length] && word.equals(s.substring(i - length, i))) {
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }

    public boolean wordBreak_v1(String s, List<String> wordDict) {
        int n = s.length();
        char[] mem = new char[n + 1];
        Arrays.fill(mem, '2');
        return dfs(s, 0, wordDict, mem) == '1';
    }

    public char dfs(String s, int i, List<String> wordDict, char[] mem) {
        int n = s.length();
        if (i == n) {
            return '1';
        }
        if (mem[i] != '2') {
            return mem[i];
        }
        for (String word : wordDict) {
            if (s.startsWith(word, i) && '1' == dfs(s, i + word.length(), wordDict, mem)) {
                return mem[i] = '1';
            }
        }
        return mem[i] = '0';
    }
}

性能

最快的解法是使用记忆化搜索，可以剪枝缩小搜索范围。

2713.矩阵中严格递增的单元格数

目标

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。

从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。

返回一个表示可访问单元格最大数量的整数。

示例 1：

输入：mat = [[3,1],[3,4]]
输出：2
解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。

示例 2：

输入：mat = [[1,1],[1,1]]
输出：1
解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。

示例 3：

输入：mat = [[3,1,6],[-9,5,7]]
输出：4
解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。

说明：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • -10^5 <= mat[i][j] <= 10^5

思路

有一个二维矩阵，我们可以从任意元素出发到达同行或同列的任意严格大于该元素值的位置，问我们最多能访问到多少单元格。

最直接的想法就是建立一个有向无环图，然后求最大路径长度。但是建图的过程需要循环mn(m+n)次，针对每个元素判断其同行同列上严格大于的元素。显然会超时。

于是考虑使用记忆化搜索，结果测试用例 558/566 超时，这个二维数组只有一行，有 100000列，从 1~100000，我在本地测试的时候报栈溢出。

我想要将其转为迭代的形式，但是时间紧迫，简单起见对一行或一列的情况做了特殊处理，排序后去重，最后勉强通过了。

官网题解使用的是动态规划，有时间详细看一下。//todo

代码

/**
 * @date 2024-06-19 16:28
 */
public class MaxIncreasingCells2713 {

    public int maxIncreasingCells(int[][] mat) {
        int res = 0;
        int m = mat.length;
        int n = mat[0].length;
        if (m == 1) {
            res = n;
            Arrays.sort(mat[0]);
            for (int i = 1; i < n; i++) {
                if (mat[0][i] == mat[0][i - 1]) {
                    res--;
                }
            }
            return res;
        } else if (n == 1) {
            res = m;
            Arrays.sort(mat, (a, b) -> a[0] - b[0]);
            for (int i = 1; i < m; i++) {
                if (mat[i][0] == mat[i - 1][0]) {
                    res--;
                }
            }
            return res;
        }

        int l = m * n;
        // 将二维坐标映射到一维，dp记录的是从该点为起点的能移动的最大次数
        int[] dp = new int[l];
        Arrays.fill(dp, -1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, move(mat, mat[i][j], i * n + j, i, j, dp));
            }
        }
        return res;
    }

    public int move(int[][] mat, int curVal, int next, int i, int j, int[] dp) {
        int m = mat.length;
        int n = mat[0].length;
        if (dp[next] > -1) {
            return dp[next];
        } else if (dp[next] == -2) {
            return 1;
        }
        boolean noNext = true;
        for (int k = 0; k < n; k++) {
            if (mat[i][k] > curVal) {
                noNext = false;
                dp[next] = Math.max(dp[next], move(mat, mat[i][k], i * n + k, i, k, dp) + 1);
            }
        }
        for (int k = 0; k < m; k++) {
            if (mat[k][j] > curVal) {
                noNext = false;
                dp[next] = Math.max(dp[next], move(mat, mat[k][j], k * n + j, k, j, dp) + 1);
            }
        }
        if (noNext) {
            dp[next] = -2;
            return 1;
        }

        return dp[next];
    }

}

性能

2786.访问数组中的位置使分数最大

目标

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

  • 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
  • 对于你访问的位置 i ，你可以获得分数 nums[i] 。
  • 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。

请你返回你能得到的 最大 得分之和。

注意 ，你一开始的分数为 nums[0] 。

示例 1：

输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。
对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。
总得分为：2 + 6 + 1 + 9 - 5 = 13 。

示例 2：

输入：nums = [2,4,6,8], x = 3
输出：20
解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。
总得分为：2 + 4 + 6 + 8 = 20 。

说明：

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

思路

给定一个数组 nums 与 正整数 x，从下标 0 开始，允许从任意位置 i 开始向后访问位置 j，如果nums[i] 与 nums[j] 的奇偶性相同，则可以获得 nums[j] 分，否则获得 nums[j] - x 分。求能够获得的分数总和的最大值。

刚开始就想到要从后向前，自底向上动态规划，如果当前的奇偶性与与后面的奇偶性相同就累加，否则就将后面的值减去x。接着又想到并不是要每一个节点都要访问，如果节点没有访问奇偶性和谁比较呢？并且后面的得分取决于前一个元素的奇偶性，考虑到昨天的题 子序列最大优雅度，觉得可能方向又错了。

于是就尝试贪心算法，从下标0开始，执行while循环，如果后面的元素奇偶性与之相同，直接累加。对于奇偶性不同的，我们可以考虑累加或者跳过。这样问题就变成了从这个新位置开始向后能获取的最大分数。注意新的位置奇偶性发生了变化。

这么一想问题又变成记忆化搜索了，于是就可以转换为递推/动态规划问题。

// todo 转换为动态规划的写法

代码

/**
 * @date 2024-06-14 8:43
 */
public class MaxScore2786 {

    public long maxScore(int[] nums, int x) {
        int n = nums.length;
        long[][] mem = new long[n + 1][2];
        for (int i = 0; i < mem.length; i++) {
            mem[i] = new long[]{Integer.MIN_VALUE, Integer.MIN_VALUE};
        }
        long res = nums[0];
        int flag = nums[0] % 2;
        int i = 1;
        while (i < n && nums[i] % 2 == flag) {
            res += nums[i];
            i++;
        }
        res += Math.max(0, maxScore(nums, x, i, flag, mem));
        return res;
    }

    public long maxScore(int[] nums, int x, int start, int preFlag, long[][] mem) {
        int n = nums.length;
        if (start >= n) {
            return 0;
        }
        // 如果选择该节点
        int flag = nums[start] % 2;
        long select = nums[start];
        if (preFlag != flag) {
            select -= x;
        }
        int i = start + 1;
        while (i < n && nums[i] % 2 == flag) {
            select += nums[i];
            i++;
        }
        if (mem[i][flag] == Integer.MIN_VALUE) {
            mem[i][flag] = maxScore(nums, x, i, flag, mem);
        }
        select += Math.max(0, mem[i][flag]);
        // 如果跳过该节点
        if (mem[start + 1][preFlag] == Integer.MIN_VALUE) {
            mem[start + 1][preFlag] = maxScore(nums, x, start + 1, preFlag, mem);
        }
        return Math.max(select, mem[start + 1][preFlag]);
    }

}

性能

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}));

    }

性能