月度归档： 2026 年 8 月

3731.找出缺失的元素

目标

给你一个整数数组 nums ，数组由若干 互不相同 的整数组成。

数组 nums 原本包含了某个范围内的 所有整数 。但现在，其中可能 缺失 部分整数。

该范围内的 最小 整数和 最大 整数仍然存在于 nums 中。

返回一个 有序 列表，包含该范围内缺失的所有整数，并 按从小到大排序。如果没有缺失的整数，返回一个 空 列表。

示例 1：

输入： nums = [1,4,2,5]
输出： [3]
解释：
最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。其中只有 3 缺失。

示例 2：

输入： nums = [7,8,6,9]
输出： []
解释：
最小整数为 6，最大整数为 9，因此完整的范围为 [6,7,8,9]。所有整数均已存在，因此没有缺失的整数。

示例 3：

输入： nums = [5,1]
输出： [2,3,4]
解释：
最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。缺失的整数为 2、3 和 4。

说明：

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 100

思路

有一个元素互不相同的数组，原本包含了 [min, max] 之间的所有整数，现在缺失了 (min, max) 中的一些元素，找到并返回缺失的元素。

首先找到数组的 min 与 max，将元素放入哈希表，遍历 (min, max) 判断数字是否在集合中。

代码


/**
 * @date 2026-08-04 8:49
 */
public class FindMissingElements3731 {

    public List<Integer> findMissingElements(int[] nums) {
        int min = 101, max = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
            set.add(num);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = min + 1; i < max; i++) {
            if (!set.contains(i)) {
                res.add(i);
            }
        }
        return res;
    }
}

性能

1406.石子游戏III

目标

Alice 和 Bob 继续他们的石子游戏。几堆石子 排成一行 ，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。

如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，分数相同返回 "Tie" 。

示例 1：

输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]
输出："Tie"
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

说明：

  • 1 <= stoneValue.length <= 5 * 10^4
  • -1000 <= stoneValue[i] <= 1000

思路

几堆石子排成一排，stoneValue[i] 表示第 i 堆石子的个数。Alice 与 Bob 轮流取石子，Alice 先取，每次可以从剩余的石子堆中取走前 1、2 或者 3 堆石子，直到石子均被取走。返回结束时取走石子最多的玩家姓名，如果相同则返回 Tie。

定义 dp[i] 表示剩余 [i, n - 1] 堆石子，先手与后手所能获得的石子个数之差的最大值。dp[i] = max(sumj - dp[j + 1])，其中 j ∈ [i, min(i + 2, n - 1)]，sumj 表示 [i, j] 的石子堆数量之和。倒序遍历，初始化 dp[n] = 0, dp[n - 1] = stoneValue[n - 1]。

代码


/**
 * @date 2026-08-03 15:22
 */
public class StoneGameIII1406 {

    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[n] = 0;
        dp[n - 1] = stoneValue[n - 1];
        for (int i = n - 1; i >= 0; i--) {
            int sum = 0;
            for (int j = i; j < Math.min(n, i + 3); j++) {
                sum += stoneValue[j];
                dp[i] = Math.max(dp[i], sum - dp[j + 1]);
            }
        }
        if (dp[0] == 0) {
            return "Tie";
        }
        return dp[0] > 0 ? "Alice" : "Bob";
    }
}

性能

877.石子游戏

目标

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

示例 1：

输入：piles = [5,3,4,5]
输出：true
解释：
Alice 先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。
如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。

示例 2：

输入：piles = [3,7,2,3]
输出：true

说明：

  • 2 <= piles.length <= 500
  • piles.length 是 偶数
  • 1 <= piles[i] <= 500
  • sum(piles[i]) 是 奇数

思路

有偶数堆石子排成一行，piles[i] 表示第 i 堆石子的数量，石子总数为奇数。从 Alice 开始，与 Bob 轮流取走左侧或右侧的整堆石子，直到取走所有石子堆为止。获得石子最多的玩家获胜。假设 Alice 与 Bob 都能做出最优的选择，判断 Alice 能否获胜。

定义 dp[i][j] 表示剩余石堆为 [i, j] 时，先手与后手获得的石子数量之差的最大值。dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])。

  • 先手 A 选择 i，剩余问题变成 B 先手 [i + 1, j]，而当前问题的先手是 A，剩余问题则是 B - A，应该取相反数。
  • 先手 A 选择 j 同理。

外层倒序遍历，内存正序遍历。因为 i 依赖 i + 1，j 依赖 j - 1。初始化 dp[i][i] = pilesp[i]。

本题使用了空间优化，当前状态是从下方与左侧转移而来，从右下角到左上对角线开始，从左向右更新。每次状态更新只用到了下方与左侧的值，因此可以使用滚动数组保存下方的值。

先手玩家必定可以获胜，首先石子总数为奇数（不可能平局），奇数堆与偶数堆的石子数量必定不同，先手可以控制自己只选择偶数堆或者奇数堆，因此必胜。

因为开始时首尾的奇偶性不同，偶，……，奇，如果奇数堆的石子更多，那么先手就选奇数堆，这时留给后手的只有首尾的两个偶数下标。

代码


/**
 * @date 2026-08-03 14:45
 */
public class StoneGame877 {

    public boolean stoneGame_v1(int[] piles) {
        return true;
    }

    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[] dp = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = piles[i];
            for (int j = i + 1; j < n; j++) {
                dp[j] = Math.max(piles[i] - dp[j], piles[j] - dp[j - 1]);
            }
        }
        return dp[n - 1] > 0;
    }
}

性能

486.预测赢家

目标

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

输入：nums = [1,5,2]
输出：false
解释：一开始，玩家 1 可以从 1 和 2 中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。 
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 false 。

示例 2：

输入：nums = [1,5,233,7]
输出：true
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。

说明：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 10^7

思路

有一个整数数组 nums，玩家1 先手，从数组任意一端取走一个元素累加到他的得分上，最终积分高的玩家获胜（如果积分相同则先手玩家获胜），每个玩家的玩法都会使他的积分最大，判断 玩家1 能否取得胜利。

定义 dp[i][j] 表示子数组 nums[i:j] 先手玩家与后手玩家所能获得的最大积分之差的最大值。dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])。

代码


/**
 * @date 2026-08-03 14:12
 */
public class PredictTheWinner486 {

    public boolean predictTheWinner_v1(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = nums[i];
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }

}

性能