簡介： 演算法面試真題詳解：硬幣排成線

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

原文：https://developer.aliyun.com/article/780282?spm=5176.8068049.0.0.55746d19rtnqyn&groupCode=ai