LeetCode292. Nim 游戏(Java版)简单的一题居然可以看出那么多思想

292. Nim 游戏

你和你的朋友,两个人一起玩 Nim 游戏:

  • 桌子上有一堆石头。
  • 你们轮流进行自己的回合,你作为先手。
  • 每一回合,轮到的人拿掉 1 - 3 块石头。
  • 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数,来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢,返回 true;否则,返回 false

示例 1:

输入:n = 4
输出:false
解释:如果堆中有 4 块石头,那么你永远不会赢得比赛;
因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。

示例 2:

输入:n = 1
输出:true

示例 3:

输入:n = 2
输出:true

提示:

  • 1 <= n <= 231 - 1

思路

我有一个朋友是ACM的银牌得主,知道巴什博弈不过分吧。

1)方法一:巴什博弈

在先取完者胜的巴什博弈中,若n可被m+1整除,则后手方必胜,否则先手方必胜。

详细的策略分析参考百度百科:巴什博弈

LeetCode292. Nim 游戏(Java版)简单的一题居然可以看出那么多思想
在题目中一次最多可以拿3个石头,所以上图的m = 3;

代码

class Solution {

    /**
     * 方法:巴什博弈
     * 时间复杂度、空间复杂度:O(1)
     *
     * @param n 石头总数
     */
    public boolean canWinNim(int n) {
        return bashGame(n, 3);
    }

    /**
     * 巴什博弈
     *
     * @param totalCount 石头总数
     * @param topStep    一次最多可以拿的石头个数
     */
    private boolean bashGame(int totalCount, int topStep) {
        // 先手获胜的结果
        return totalCount % (topStep + 1) != 0;
    }
}

2)方法二:暴力递归(会超时)

找规律,多写几个数就能找到规律:

依照题意,令函数f(n)表示n个石子能否获胜。则f(n) = !f(n-1) or !f(n-2) or !f(n-3) ;

  • 因为f(n-1)表示朋友能否赢,而我的状态与之相反;
  • 又在取1、2、3个石头操作中,只要有一个策略能赢即可。 嘿嘿,这不是典型的递归公式嘛。

代码

public boolean canWinNim(int n) {
    if(n<=3) {
        return true;
    } else {
        // 不管我先拿1个、2个、3个石头,后手都能赢;否则先手的我赢
        return !(canWinNim1(n-1) && canWinNim1(n-2) && canWinNim1(n-3));
    }
}

递归超时的原因?

自顶向下的递归,反复用到了大量重复数据,导致了不必要的开销。

解决重复数据的方法:

  • 1、用记忆化数组存储用到过的数据,减少不必要的开销。即下面的 方法三:动态规划
  • 2、迭代,使用几个变量代替动态规划的数组。即下面的方法四:迭代

3)方法三:动态规划(有可能超出内存限制)

用记忆化数组dp存储用到过的数据;但当n很大时,可能会超出内存限制

public boolean canWinNim(int n) {
    if(n <= 3) return true;
    boolean[] dp = new boolean[n+1];
    dp[1] = true;
    dp[2] = true;
    dp[3] = true;

    for (int i = 4; i <= n; i++) {
        // 不管我先拿1个、2个、3个石头,后手都能赢;否则先手的我赢
        dp[i] = !(dp[i-1]&&dp[i-2]&&dp[i-3]);
    }
    return dp[n];
}

开辟数组dp有点浪费内存空间,因为自底向上的方法中并不需要存储之前用到过的很多数据,它是逐步向前的,而与当前这一步有关的值只有前三个数。

3)方法四:迭代(有可能超时)

使用四个变量(a、b、c、temp)代替动态规划dp数组,释放不必要的内存空间占用;当n很大时,仍然可能会超时

public boolean canWinNim(int n) {
    if(n <= 3) return true;
    boolean a=true;
    boolean b=true;
    boolean c=true;
    boolean temp;
    for (int i = 4; i <= n; i++) {
        // 不管我先拿1个、2个、3个石头,后手都能赢;否则先手的我赢
        temp = !(a && b && c);
        a = b;
        b = c;
        c = temp;
    }
    return c;
}
上一篇:leetcode:292.Nim游戏


下一篇:【坚持每日一题9.18】Nim 游戏