shelterofly

目标

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

性能

目标

给你一个整数数组 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;
    }

}

性能

目标

给你一个字符串 word，由小写英文字母组成。

电话键盘上的按键与 不同 小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。

现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母，但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。

返回重新映射按键后输入 word 所需的 最少 按键次数。

下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不 对应任何字母。

示例 1：

输入：word = "abcde"
输出：5
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。

示例 2：

输入：word = "xyzxyzxyzxyz"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 3 上按一次
"z" -> 在按键 4 上按一次
总成本为 1 * 4 + 1 * 4 + 1 * 4 = 12 。
可以证明不存在其他成本更低的映射方案。
注意按键 9 没有映射到任何字母：不必让每个按键都存在与之映射的字母，但是每个字母都必须映射到按键上。

示例 3：

输入：word = "aabbccddeeffgghhiiiiii"
输出：24
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
"f" -> 在按键 7 上按一次
"g" -> 在按键 8 上按一次
"h" -> 在按键 9 上按两次
"i" -> 在按键 9 上按一次
总成本为 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24 。
可以证明不存在其他成本更低的映射方案。

说明：

• 1 <= word.length <= 10^5
• word 仅由小写英文字母组成。

思路

可以将 26 个字母映射到 2 ~ 9 按键上，比如将 abc 映射到 2，那么输入 b 需要按两下 2，输入 c 需要按三下 2。给定一个单词 word，返回输入该字符所需的最少按键次数。

与 3014.输入单词需要的最少按键次数I 相比，本题并没有说 word 是由不同字母组成。

将字母出现频次从大到小排序，大的优先分配在按键的第一个位置（按一下），然后是第二个位置（按两下），以此类推。

代码

/**
 * @date 2026-07-31 9:02
 */
public class MinimumPushes3016 {

    public int minimumPushes(String word) {
        int[] cnt = new int[26];
        for (char c : word.toCharArray()) {
            cnt[c - 'a']++;
        }
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < 26; i++) {
            q.offer(new int[]{i, cnt[i]});
        }
        int k = 0;
        int res = 0;
        for (int i = 0; i < 26; i++) {
            int[] e = q.poll();
            if (e[1] == 0) {
                break;
            }
            res += (k++ / 8 + 1) * e[1];
        }
        return res;
    }
}

性能

目标

给你一个 回文 字符串 s。

返回 s 的按字典序排列的 最小 回文排列。

如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个 回文 字符串。

排列 是字符串中所有字符的重排。

如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。

如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。

示例 1：

输入： s = "z"
输出： "z"
解释：
仅由一个字符组成的字符串已经是按字典序最小的回文。

示例 2：

输入： s = "babab"
输出： "abbba"
解释：
通过重排 "babab" → "abbba"，可以得到按字典序最小的回文。

示例 3：

输入： s = "daccad"
输出： "acddca"
解释：
通过重排 "daccad" → "acddca"，可以得到按字典序最小的回文。

说明：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成。
• 保证 s 是回文字符串。

思路

有一个回文字符串 s，将其重新排列成回文字符串，使得字典序最小。

记录字符串中字符的出现次数，然后按字典序从两边向中间填充，如果出现次数为奇数，那么该字符为中间元素。

代码

/**
 * @date 2026-07-28 9:03
 */
public class SmallestPalindrome3517 {

    public String smallestPalindrome(String s) {
        int[] cnt = new int[26];
        int n = s.length();
        char[] res = new char[n];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        char mid = 0;
        int cur = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                mid = (char) ('a' + i);
            }
            int k = cnt[i] / 2;
            char c = (char) ('a' + i);
            for (int j = 0; j < k; j++) {
                res[cur + j] = c;
                res[n - cur - j - 1] = c;
            }
            cur += k;
        }
        if (n % 2 == 1) {
            res[n / 2] = mid;
        }
        return new String(res);
    }

}

性能