当前位置 博文首页 > qq_45162113的博客：<LeetCode>三道脑筋急转弯编程题
class Solution {
public boolean stoneGame(int[] piles) {
return piles.length%2==0;
}
}
注意：本题存在一些漏洞，比如当数组第一层存在一个大于其他数总和的数时，只要第一个人拿到该数，则不管数组长度为多少都是该玩家获胜。或着当数组每个元素数字相等，胜利的条件就成了拿的次数。
292.Nim游戏
你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
示例：
输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
解题思路：
这一题可以尝试从1往后枚举归纳的去寻找题解，1，2，3，4只有4是输掉；
然后5，6，7，8的时候通过最优解让对方去得到4即可，可推知8的情况下是失败的；进而可以推知4的倍数都是无法通过最优操作推到1，2，3，既4的倍数石子会输掉。
代码如下：
class Solution {
public boolean canWinNim(int n) {
return n%4!=0;
}
}
1025.除数博弈
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
示例：
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
解题思路：
数字N如果是奇数，它的约数必然都是奇数；若为偶数，则其约数可奇可偶。
无论N初始为多大的值，游戏最终只会进行到N=2时结束，那么谁轮到N=2时谁就会赢。因为爱丽丝先手，N初始若为偶数，爱丽丝则只需一直选1，使鲍勃一直面临N为奇数的情况，这样爱丽丝稳赢；N初始若为奇数，那么爱丽丝第一次选完之后N必为偶数，那么鲍勃只需一直选1就会稳赢。综述，判断N是奇数还是偶数，即可得出最终结果！
代码如下：
class Solution {
public boolean divisorGame(int N) {
return N%2==0;
}
}
