LeetCode 292: Nim Game

Difficulty: Easy

Tags: Brainteaser

问题描述

Nim游戏的规则是：桌子上有一堆石子一共n个，你和小明轮流从石子堆中取石子，一次可以取1~3个石子。取到最后一个石子的人赢得游戏。你是先手，小明后手。当然你和小明取石子的策略都是最优的。

解决方案

这个问题的关键在于思考在石子个数在多少个的时候你会赢或者输。

当石子个数小于等于3的时候，你是必胜的；当石子个数为4的时候，你就会输了，因为不管你取几个，小明都可以取到第4个石子。

那个下一个危险的石子个数是多少呢？8, 12, 16…是4的倍数。

当石子个数为4的倍数的时候，不管你一次取几个(假设为i个)，小明都可以取j个，来使i+j=4，从而让你必输。

当石子个数不为4的倍数的时候，因为我们已经知道先手并且石子个数为4的倍数的话必输，那么你可以先取几个让石子堆的个数为4的倍数，这时候是小明取石子，可以理解为小明为『先手』而此时的石子堆个数为4的倍数，那么小明必输，你必胜。

引申一下这个游戏，当你一次最多可以取m个石子的时候，那么m+1对于你来说就是危险数字(death number)，石子个数为m+1的倍数的时候并且你先手的时候你必输。

▷ Time Complexity: O(1)

▷ Space Complexity: O(1)

1
2
3
4
5
6
7
8
9

class Solution {
public:
    bool canWinNim(int n) {
        if(n%4 == 0)
            return false;
        else
            return true;
    }
};

回到 Conquer Leetcode