LeetCode: Nim Game

时间:2022-06-12 14:12:15

这题其实不太好想,用到了博弈论

1,2,3 能赢

4 输

5,6,7 赢

8 输

9,10,11 赢

12 输

那么结论就是4的倍数就是输,其他情况就能赢。

为什么会是这样呢?很好解释,根源就在4会输,那么5,6,7就会凑到4,让对方输,那对方也会这么想,8的时候无论你拿1,2,3块对方都会凑4

如果是9,10,11,就拿1,2,3凑8,依次推论,只要第一次拿的时候凑到4的整数就行,下面对方拿多少还是凑到4的整数,最后到4对方还是要输。

 public class Solution {
public boolean canWinNim(int n) {
return !(n % 4 == 0);
}
}