前往
大廳
主題

LeetCode - 1510. Stone Game IV 解題心得

Not In My Back Yard | 2022-08-25 12:00:04 | 巴幣 2 | 人氣 158

題目連結:


題目意譯:
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 值便可以直接回傳對應的答案。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作