写点什么

【LeetCode】石子游戏 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 06 月 16 日

题目描述

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。


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


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


假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。


示例:
输入:[5,3,4,5]输出:true解释:亚历克斯先开始,只能拿前 5 颗或后 5 颗石子 。假设他取了前 5 颗,这一行就变成了 [3,4,5] 。如果李拿走前 3 颗,那么剩下的是 [4,5],亚历克斯拿走后 5 颗赢得 10 分。如果李拿走后 5 颗,那么剩下的是 [3,4],亚历克斯拿走后 4 颗赢得 9 分。这表明,取前 5 颗石子对亚历克斯来说是一个胜利的举动,所以我们返回 true 。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/stone-game著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 这个题目很有意思,值得多做几次。双方交替选择石头,最终获取石头数量多的获胜。

  • 首先可以使用程序模拟题目过程,代码如下:


    public boolean stoneGame(int[] piles) {        int aStoneNum = 0, bStoneNum = 0;        int left = 0;        int right = piles.length - 1;        boolean aFlag = true;        while (left < right) {            int temp = Math.max(piles[left], piles[right]);            if (piles[left] >= piles[right]) {                left++;            } else {                right--;            }
if (aFlag) { aStoneNum += temp; aFlag = false; } else { bStoneNum += temp; aFlag = true; } } return aStoneNum > bStoneNum; }
复制代码


这样模拟有一个弊端,就是只考虑了当前的最优解,但不一定是全局的最优解,没有通过全部测试用力。


  • 因此,采用动态规划的方式求解,动态判断最优解。

AC 代码

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


上述的转移方程是


dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
复制代码


这样就能确定最优解。

总结

  • 动态规划算法的时间复杂度是 O(n * n), 空间复杂度是 O(n)

  • 坚持每日一题,加油!

发布于: 2021 年 06 月 16 日阅读数: 8
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】石子游戏Java题解