描述

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。 请判定 ### 先手玩家 必胜还是必败? 若必胜, 返回 true, 否则返回 false.

在线评测地址

样例 1:

输入: 1 输出: true 

样例 2：

输入: 4 输出: true 解释:  先手玩家第一轮拿走一个硬币, 此时还剩三个. 这时无论后手玩家拿一个还是两个, 下一次先手玩家都可以把剩下的硬币拿完. 

挑战

O(1) 时间复杂度且 O(1) 存储。

算法

博弈（巴什博弈）

算法分析

有 nn 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。本题要求判断先手玩家必胜还是必败。 我们可以根据 nn 的取值不同分为必败态和必胜态。不妨先从小规模分析： (1) n=1n=1 或 n=2n=2 时，先手玩家可以 1 次将所有硬币拿走，先手必胜。 (2) n=3n=3 时，先手玩家拿走 1 个，则后手玩家拿走 2 个；先手玩家拿走 2 个，则后手玩家拿走 1 个；先手必败。 (3) n=4n=4 时，先手玩家先拿走 1 个，此时对于后手玩家来说，他剩下 3 个，面临着 (2) 的情况。根据 (2) 的分析，先手必胜。 (4) n=5n=5 时，先手玩家先拿走 2 个，此时对于后手玩家来说，他面临着 (2) 的情况。根据 (2) 的分析，先手必胜。 (5) n=6n=6 时,无论先手玩家怎么取 x 个，后手玩家都可以取 3-x 个，另先手玩家剩下 3 个，面临着 (2) 的情况。根据 (2) 的分析，先手必胜。

由上述分析当 n=1,2,4,5n=1,2,4,5 时为必胜态，当 n=3,6n=3,6 时为必败态。同时，必胜态和必败态之间是有关联的。对于先手玩家而言，只要他一开始面临的不是必败态，他每一步都可以将必败态留给后手玩家，最后获得胜利。对于这个游戏来说，必败态是 n%3==0n%3==0，必胜态是 n%3≠0n%3≠0 。先手玩家每次取后都令 n%3==0n%3==0 即可胜利。 拓展知识：* 这道题目属于 巴什博弈 模型：一堆 n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个。最后取光者得胜。先手玩家要必胜，则一开始 n%(m+1)≠0n%(m+1)≠0 。在本题中，m=2m=2 。

复杂度分析

时间复杂度：O(1)O(1) 空间复杂度：O(1)

public class Solution {      /**       * @param n: An integer       * @return: A boolean which equals to true if the first player will win       */      public boolean firstWillWin(int n) {          if (n % 3 != 0)              return true;          else              return false;      }  } 

更多题解参考

大佬有話說 (0)