leetcode [#292]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

---

解决方案

public static boolean canWinNim(int n){
    if (n % 4 != 0){
        return true;
    } else {
        return false;
    }
}

---

注意事项

　　思路是递归，弱化问题，考虑：
如果石子数量少1个会输的话，那么现在一定会赢（通过先取走1个石子的办法）；
如果石子数量少2个会输的话，那么现在一定会赢（通过先取走2个石子的办法）；
如果石子数量少3个会输的话，那么现在一定会赢（通过先取走3个石子的办法）。

　　故也可以如下实现：

public static boolean canWinNim(int n){
    if(n==1 || n==2 || n==3){
        return true;
    } else {
        if(!canWinNim(n-1) || !canWinNim(n-2) || !canWinNim(n-3)) return true;
        return false;
    }
}