Leetcode292. 分治法解决Nim Game

xiaoxiao2021-02-28  7

Leetcode292. Nim Game

题目

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.

解题分析

通过题目大意我们可以大概知道:你和你的朋友在玩一个叫Nim的游戏,桌上有一堆石头,每人一次只能摸1~3颗石头,谁拿到桌上的最后一颗石头谁就取得游戏的胜利,其中你先摸石头。题目要求我们写一个函数来根据桌上石头的数目来确定你自己是否可以赢得游戏。

一眼看过去,感觉这道题肯定是又有什么很高深的算法,想解出这道题是很有难度的,然而,当你静下心来研究,你就会发现这道题其实非常的简单,且听我细细道来。

我们可以先从石头的数目为1开始想下这道题目。很显然,当石头的数目为1、2、3时,你可以一把拿完桌上所有的石头从而取得胜利;当石头的数目为4时,无论你拿多少颗石头,对方都会拿走最后一颗石头,从而赢得游戏。 根据前面的启发,从5开始,我们可以采用分治的算法,将题目细小化处理。由5=1+4,我们可以先取一颗石头,此时桌上剩下4颗石头,根据前面的分析我们知道,当石头数目为4时后取石头的人最终将会赢得胜利,因此这种情况下我们就可以赢了。同样,6=2+4,7=3+4都可以这样分析。 再分析一下石头数目为8的情况。8=4+4,由于对方也想取得胜利,因此无论你第一次拿走多少颗石头,对方都会确保在自己第一次拿走石头后桌上石头剩余数目为4,因此对方就赢了。

依此类推,所有石头数目大于4的情况都可以这样考虑,通过前面的分析我们可以知道,当石头数目为4的倍数时,对方取得胜利;而其他情况下你都可以赢得游戏。因此,这道题到最后实际上就转化为一个非常简单的问题,就是判断石头的数目是否为4的倍数,如果是,返回false;如果不是,返回true。

源代码

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

这样看很简单吧,时间复杂度为O(1),简单得不能再简单了。 这只是我对这道题的一些想法,有问题还请在评论区讨论留言~

转载请注明原文地址: https://www.6miu.com/read-450338.html

最新回复(0)