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