描述
有 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;

    }

}

更多题解参考：九章官网solution