标签： 组合

目标

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

说明:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

思路

数组 nums 的元素表示可以向后跳跃的最大长度，求从 0 跳到 n - 1 所需的最小跳跃次数。

定义 dp[i] 表示到达下标 i 所需的最小跳跃次数，状态转移方程为 dp[i + k] = min(dp[i] + 1)，其中 k ∈ [1, nums[i]]。

代码

/**
 * @date 2024-03-07 17:14
 */
public class CanJumpII45 {

    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 0x3f3f3f);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n && j <= i + nums[i]; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }

}

性能

目标

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

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

说明:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

思路

有一个数组 candidates，用 candidates 中的元素值组成目标值 target，返回每种组合的元素列表。数组中的每个元素在每种组合中只能使用一次。

考虑是否选择某个元素，可能的组合有 2^n 种。但是题目有条件限制，要求组合元素值之和等于target，那么如果组合的和大于 target 可以提前返回。因此可以将 candidates 从小到大排序，回溯。关键是如何去除重复组合，对于相同的元素，只关心取的个数，因此如果不选某个元素，后续相同的元素也都不能选。

代码

/**
 * @date 2025-01-26 15:24
 */
public class CombinationSum40 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, 0, target, candidates, path, res);
        return res;
    }

    public void dfs(int index, int sum, int target, int[] candidates, List<Integer> path, List<List<Integer>> res) {
        if (sum == target) {
            List<Integer> tmp = new ArrayList<>(path);
            res.add(tmp);
            return;
        }
        if (index == candidates.length || sum > target) {
            return;
        }
        int cur = candidates[index];
        path.add(cur);
        dfs(index + 1, sum + cur, target, candidates, path, res);
        path.remove(path.size() - 1);
        index++;
        // 如果不选当前的值，也同样不选后续所有相同的值
        // 对于相同的值，只考虑选了几个，如果这里不跳过，就会出现重复
        // 比如有4个相同的值，选 选 不选 不选，如果允许后续再次选择，就会出现
        // 选 不选 不选 选、
        // 选 不选 选 不选
        // 不选 选 选 不选、
        // 不选 选 不选 选、
        // 不选 不选 选 选、
        while (index < candidates.length && cur == candidates[index]) {
            index++;
        }
        dfs(index, sum, target, candidates, path, res);
    }
}

性能

目标

给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。

整天 定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：

输入： hours = [12,12,30,24,24]
输出： 2
解释：
构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]
输出： 3
解释：
构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

说明：

• 1 <= hours.length <= 5 * 10^5
• 1 <= hours[i] <= 10^9

思路

有一个整数数组 hours，返回 hours[i] + hours[j] % 24 == 0，i < j 的下标对的个数。

与昨天的题目 3184.构成整天的下标对数目I 相比，数据规模从 100 变成了 5 * 10^5。枚举下标对的时间复杂度为 O(C(n,2))，即 O(n^2)，肯定会超时。

题目并不要求输出具体的下标对，只需要计数即可。当枚举右端点时，如果可以直接获取到已访问过的元素中，能够与当前元素组成合法下标对的元素个数，那么整体的时间复杂度可以降为 O(n)。定义 cnt[m] 表示已访问过的元素中对 24 取余后值为 m 的元素个数。当枚举到元素 i 时，只需累加 cnt[24 - nums[i] % 24] 即可。

代码

/**
 * @date 2024-10-23 10:16
 */
public class CountCompleteDayPairs3185 {

    public long countCompleteDayPairs_v2(int[] hours) {
        long res = 0L;
        int[] cnt = new int[24];
        int zeroCnt = 0;
        for (int hour : hours) {
            int m = hour % 24;
            if (m == 0) {
                res += zeroCnt;
                zeroCnt++;
            } else {
                res += cnt[24 - m];
                cnt[m]++;
            }
        }
        return res;
    }

}

性能

目标

现有一份 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;
    }
}

性能