mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
20 lines
695 B
Markdown
20 lines
695 B
Markdown
# [292. Nim Game](https://leetcode.com/problems/nim-game/)
|
||
# 思路
|
||
A、B人交替数数，每个人每次只能数1、2、或3个数，谁先数到n谁赢，A先数。AB两人都想自己赢。
|
||
* 若n = 1、2或3, 那么A肯定赢;
|
||
* 若n = 4, 那么不管A数1、2还是3个数A都会输;
|
||
* 若n = 5、6或7, 那么A可以分别数1、2和3个数然后转换成n = 4且B先数的情况，则最终A赢；
|
||
* 若n = 8, 那么不管A数完第一次后n = 5、6、7，然后该B数，由上条分析知最终A输；
|
||
* ......
|
||
|
||
由此可见，当n是4的倍数时A会输，否则赢。
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
bool canWinNim(int n) {
|
||
return !(n % 4 == 0);
|
||
}
|
||
};
|
||
```
|