題目
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
解題思路
題目大意是你跟另一玩家玩石頭游戲叽赊，規(guī)則如下：桌子上有一堆石頭昏滴，每輪每個人輪流拿1到3個石頭兴泥，拿走最后一個石頭的玩家為贏家，前提是每個玩家都會采取最佳策略來進(jìn)行這個游戲名挥，而且每次都是從你開始第一輪游戲计盒。題目給定每次游戲的石頭總數(shù)堪滨，要求你寫一個function判斷你自己是否可以贏下這場游戲计螺。
初看題目，僅僅根據(jù)游戲開始時的石頭總數(shù)就能判定最終贏家是誰冶忱，感覺好像有點(diǎn)難尾菇，一時無從下手。但一想到這題是easy題，肯定不會有多難派诬，只是一下子被題目嚇到了劳淆。于是我從抽屜抽出一張陳舊草稿紙，開始先窮舉石頭總數(shù)千埃，果然功夫不負(fù)有心人憔儿，最后發(fā)現(xiàn)這題明顯有規(guī)律。
當(dāng)石頭個數(shù)小于 4 時放可，因為第一次是你開始拿，所以贏家肯定是你朝刊。當(dāng)石頭個數(shù)等于 4 時耀里，如題中所述，不管你第一次是拿一個兩個還是三個石頭拾氓，最后一個石頭肯定是你的對手拿走冯挎，所以你肯定是輸?shù)摹Ｄ钱?dāng)石頭個數(shù)是 5 的時候呢咙鞍？很明顯房官，你第一次只需拿走一個石頭就能贏得游戲，因為當(dāng)你拿走一個石頭后续滋，就只剩下4個石頭給對手了翰守，而對手就會陷入之前的“四石頭”境地，即無論對手選擇拿幾個石頭疲酌，最后都會輸?shù)粲螒蚶濉Ｒ源祟愅疲?dāng)石頭總數(shù)是 6 和 7 個時朗恳，你只需拿走 2 和 3 個石頭就能確保自己贏得游戲湿颅。但當(dāng)石頭總數(shù)等于 8 時，無論你怎么拿都注定會陷入“四石頭”境地粥诫，所以會輸?shù)舯荣愑秃健亩罱K得出游戲規(guī)律，當(dāng)一開始的石頭總數(shù)是4的倍數(shù)的時候怀浆，你都會輸?shù)舯荣愐昵簦凑齽t可以獲得勝利。
參考代碼
class Solution {
public:
bool canWinNim(int n) {
return n % 4 != 0 ;
}
};
反思與總結(jié)
看了代碼揉稚，是不是覺得巨簡單- -秒啦。其實很多題目都是這樣，一開始可能會覺得很棘手搀玖，這時候需要自己沉下心余境，先寫出前幾個簡單實例，然后試試在其中能不能找出規(guī)律，往往答案可能會比你想象的簡單得多芳来。
