leetcodeブラシ問題292 NimゲームNim Game(簡単)Python Java
2348 ワード
タイトルの説明:
あなたとあなたの友达、二人でNimゲームをします:机の上に石がたくさんあって、毎回あなた达は交代で1-3枚の石を取ります.最後の石を取った人が勝者だ.君が先手だ. あなたたちは賢い人で、一歩一歩が最適解です.特定の石の数でゲームを勝ち取ることができるかどうかを判断する関数を作成します.
例:
入力:4 出力:false 解釈:もし山の中に4つの石があれば、あなたは永遠に試合に勝つことはありません. 1つ、2つ、3つの石を持って行っても、最後の石はいつも友达に持って行かれますから.
問題解決の考え方:
Nimゲームの解題の鍵は「必勝状態」を探すことだ.
問題に基づいて条件を設定する:
......
このようにして、結論を出すことができます.
あなたの相手が最後に取ったとき、石が4つだったら、彼が1、2、3つ持っていても、あなたは石を持っています.この点を保証するには、あなたが取るたびに石の個数が4の倍数であることを保証する必要があります.それは最初の石の数が4の倍数ではないことを意味します.
以下はJavaバージョンです.
あなたとあなたの友达、二人でNimゲームをします:机の上に石がたくさんあって、毎回あなた达は交代で1-3枚の石を取ります.最後の石を取った人が勝者だ.君が先手だ. あなたたちは賢い人で、一歩一歩が最適解です.特定の石の数でゲームを勝ち取ることができるかどうかを判断する関数を作成します.
例:
入力:4 出力:false 解釈:もし山の中に4つの石があれば、あなたは永遠に試合に勝つことはありません. 1つ、2つ、3つの石を持って行っても、最後の石はいつも友达に持って行かれますから.
問題解決の考え方:
Nimゲームの解題の鍵は「必勝状態」を探すことだ.
問題に基づいて条件を設定する:
n∈[1,3] , 。
n == 4 , , n∈[1,3] , 。
n∈[5,7] , , [1,3] , n == 4 , 。
n == 8 , , n∈[5,7] , 。
......
このようにして、結論を出すことができます.
n % 4 != 0 , ; 。
あなたの相手が最後に取ったとき、石が4つだったら、彼が1、2、3つ持っていても、あなたは石を持っています.この点を保証するには、あなたが取るたびに石の個数が4の倍数であることを保証する必要があります.それは最初の石の数が4の倍数ではないことを意味します.
class Solution:
def canWinNim(self, n):
"""
:type n: int
:rtype: bool
"""
if n % 4 == 0:
return False
return True
以下はJavaバージョンです.
public class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}