leetcodeブラシ問題292 NimゲームNim Game(簡単)Python Java

2348 ワード

タイトルの説明:
あなたとあなたの友达、二人で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;
    }
}