292. Nim Game

问题:

给n个石子,由你开始选取,和你的朋友轮流进行。

每次选取,可以选取1~3个石子,

最后一个取完石子的人获胜,返回你是否能赢得胜利。

Example 1:
Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

Example 2:
Input: n = 1
Output: true

Example 3:
Input: n = 2
Output: true
 
Constraints:
1 <= n <= 2^31 - 1

  

解法:math

我们进行反向推演:

  • 若轮到我时:
    • 最后剩下1~3个石子,那么我一定赢。
    • 剩下4个石子,那我不管取1~3个石子,我一定会留下1~3个石子,使得对方赢。

即谁面临4个石子,谁输。

 

那么假使为了让我一定赢,那么一定得使得对方面临4个石子。

  • 那么怎样才能让对方面临4个石子呢?
    • 那就是:
    • 轮到我时,让我能够面临:5~7个石子,那么我就一定能取到,使得对方面临4个石子。
  • 继续:怎样才能让我面临5~7个石子呢?
    • 那么:
    • 轮到对方时,让对方面临:8个石子,不管对方怎么取,都一定会剩下5~7个石子。

……

 

总结:

为了让我赢:那就要对方面临:4,8,12... 4n 个石子。

如果一开始就是我面临4n个石子,对方也是聪明的,对方就不会留给我,能够使得对方自己面临4n个石子的机会。

所以,只要一开始我就面临4n个石子,最后就只能输了。

否则,我就一定不会让自己接下来面临4n个石子。

 

答案即是:若4%n==0,那我就一定输,否则一定赢。

 

代码参考:

1 class Solution {
2 public:
3     bool canWinNim(int n) {
4         return n%4!=0;
5     }
6 };

 

上一篇:用 Python + Appium 的方式自动化清理微信僵尸好友


下一篇:Android开发——ListView的简单使用