Leetcode PHP题解--D64 292. Nim Game

不念不忘少年蓝@ 2022-01-16 12:45 145阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

# D64 292. Nim Game #

## 题目链接 ##

[292. Nim Game][]

## 题目分析 ##

假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿1~3颗石头。拿到最后一颗石头的一方为剩方。第一轮由你开始捡石头。  
同时假设你和你的朋友都足够聪明，每次都能采取最优策略。

现给定一个石头数量，判断你最终是否能取得胜利。

## 思路 ##

我们先从少一点开始推广到n个石头。

如果有1～3颗石头，因为规定了是你开始、还假设会采取最优策略，那么你是能获胜的。也即，对方不会在拿走石头后剩下1

假设有4颗石头。  
你拿1颗，会剩下3颗。对方全拿，**对方赢**。  
你拿2颗，会剩下2颗。对方全拿，**对方赢**。  
你拿3颗，会剩下1颗。对方全拿，**对方赢**。  
即，怎么拿都是你输。

假设有5颗石头。  
你拿1颗，会剩下4颗。  
对方拿走1颗，剩下3颗给你，你全拿，你赢。  
对方拿走2颗，剩下2颗给你，你全拿，你赢。  
对方拿走3颗，剩下1颗给你，你全拿，你赢。  
你拿2颗，会剩下3颗。对方全拿，**对方赢**。  
你拿3颗，会剩下2颗。对方全拿，**对方赢**。  
因此，这一轮你会选择拿1颗，剩下4颗。

假设有6颗石头。  
你拿1颗，会剩下5颗。  
对方拿走1颗，剩下4颗给你，参考一开始就只有4颗的情况，**对方赢**。  
对方拿走2颗，剩下3颗给你，你全拿，你赢。  
对方拿走3颗，剩下2颗给你，你全拿，你赢。  
你拿2颗，会剩下4颗。  
对方拿走1颗，剩下3颗给你，你全拿，你赢。  
对方拿走2颗，剩下2颗给你，你全拿，你赢。  
对方拿走3颗，剩下1颗给你，你全拿，你赢。  
你拿3颗，会剩下3颗。对方全拿，**对方赢**。  
因此，这一轮你会选择拿2颗，剩下4颗。

假设有7颗石头。  
你拿1颗，会剩下6颗。  
对方拿走1颗，剩下5颗给你，参考一开始就只有5颗的情况，你赢。  
对方拿走2颗，剩下4颗给你，**对方赢**。  
对方拿走3颗，剩下3颗给你，你全拿，你赢。  
你拿2颗，会剩下5颗。  
对方拿走1颗，剩下4颗给你，**对方赢**。  
对方拿走2颗，剩下3颗给你，你全拿，你赢。  
对方拿走3颗，剩下2颗给你，你全拿，你赢。  
你拿3颗，会剩下4颗。  
对方拿走1颗，剩下3颗给你，你全拿，你赢。  
对方拿走2颗，剩下2颗给你，你全拿，你赢。  
对方拿走3颗，剩下1颗给你，你全拿，你赢。  
因此，这一轮你会选择拿3颗，剩下4颗。

假设有8颗石头。  
你拿1颗，会剩下7颗。  
对方拿走1颗，剩下6颗给你，参考一开始就只有6颗的情况，你赢。  
对方拿走2颗，剩下5颗给你，参考一开始就只有5颗的情况，你赢。  
对方拿走3颗，剩下4颗给你，**对方赢**。  
你拿2颗，会剩下6颗。  
对方拿走1颗，剩下5颗给你，你赢。  
对方拿走2颗，剩下4颗给你，**对方赢。**  
对方拿走3颗，剩下3颗给你，你全拿，你赢。  
你拿3颗，会剩下5颗。  
对方拿走1颗，剩下4颗给你，**对方赢。**  
对方拿走2颗，剩下3颗给你，你全拿，你赢。  
对方拿走3颗，剩下2颗给你，你全拿，你赢。  
因此，必输无疑。

我们可以得出规律。当剩下的石头为4的整数倍、双方都采取最优策略时，先下手的一方为输家。

因此这个题目就很简单了，只要判断给定的数字是否是4的整数倍即可。

## 最终代码 ##

<?php
    class Solution {
    
        /**
         * @param Integer $n
         * @return Boolean
         */
        function canWinNim($n) {
            return $n%4!=0;
        }
    }

若觉得本文章对你有用，欢迎用[爱发电][Link 1]资助。

转载于:https://my.oschina.net/u/2246923/blog/3051109

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/ba6b0b418aaa43d4a4550d1756869382.png
[292. Nim Game]: https://leetcode.com/problems/nim-game/
[Link 1]: https://afdian.net/@skys215