題目連結:
題目意譯:
Alice 和 Bob 輪流玩著一個遊戲,其中 Alice 作為先手。
一開始在一個石堆中有著 n 顆石頭。在某位玩家的回合中,該玩家可以在一步中從石堆中移除任意非零之平方數的數量之石頭。
並且,如果一個玩家不能做出下一步,則他/她將輸掉本遊戲。
給定一正整數 n,回傳真(True)若且唯若 Alice 將會贏得遊戲;反之,則回傳假(False)。假設兩位玩家皆以最佳策略遊玩。
限制:
1 ≦ n ≦ 10 ^ 5
範例測資:
範例 1:
輸入: n = 1
輸出: true
解釋: Alice 可以移掉 1 顆石頭來贏得遊戲,因為 Bob 將無法做出任何一步。
範例 2:
輸入: n = 2
輸出: false
解釋: Alice 只可以移掉 1 顆石頭,之後 Bob 移掉最後一顆石頭並贏得遊戲(2 → 1 → 0)。
範例 3:
輸入: n = 4
輸出: true
解釋: n 本身是一個完全平方數,因此 Alice 可以在一步之中獲勝,也就是移除掉這 4 顆石頭(4 → 0).
解題思維:
跟
這種題目基本雷同,只是現在能移除的石頭數為 1(1 ^ 2)、 4(2 ^ 2)、 9(3 ^ 2)、 16(4 ^ 2)等等。而且我們可以直接建表(參見與前面同一個鏈結),看到哪個 n 值便可以直接回傳對應的答案。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。