切換
舊版
前往
大廳
主題

LeetCode - 292. Nim Game 解題心得

Not In My Back Yard | 2020-09-30 00:00:10 | 巴幣 4 | 人氣 356

題目連結:


題目意譯:
你正在與你的一個朋友玩以下之拈(Nim)的遊戲:有一個石頭堆在桌子上,每次你們之一輪番地移除 1 到 3 顆石頭。移除最後一個石頭的人即為贏家。而你一定會是第一個先移除石頭的人。

你們兩個都相當地聰明,且對於本遊戲有最佳的策略。撰寫一個函式去判斷在給定石頭堆的石頭數下,你是否可以贏此遊戲。



範例測資:
範例:
輸入: 4
輸出: false
解釋: 如果堆裡有 4 個石頭,則你一定無法贏得此局遊戲;
       不管你移除 1 、 2 或是 3 顆石頭,最後一顆石頭必定會由你的朋友移掉。



解題思維:
顯而易見地,當石頭數 = 1 、 2 或是 3 時,你必勝。

當石頭數 = 4 時,你不管拿 1 、 2 、 還是 3 顆石頭,都等價於石頭數 = 3 、 2 或是 1 且你的朋友擔任先手的狀況。因此,你必輸。

而石頭數 = 5 時,可以只拿 1 顆,使得整個遊戲等價於你的朋友為先手且石頭數為 4 。此時你的朋友必輸,因此你必贏。

同理石頭數 = 6 或 7 時,可以只拿 1 或 2 顆使得你自己必贏。

而到 8 顆石頭時,又變為必輸。

以此類推。因此可以看到當石頭數為 4 的倍數時,你必輸。其他情況下,則必贏。




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

創作回應

更多創作