| title | date | tags | |
|---|---|---|---|
除数博弈---LeetCode1025(智力题) |
2020-07-24 03:06:17 -0700 |
|
这里写题目描述爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。 用 N - x 替换黑板上的数字 N 。 如果玩家无法执行这些操作，就会输掉游戏。 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
示例 1：
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
这道题看起来很唬人，其实就是一道找规律的题。
随便列几项：
- 当alice先手为1，alice输
- 当alice先手为2，alice只能拿1，那么bob输
- 当alice先手为3，alice只能拿1，然后就成为了bob先手为2，所以alice输
- 当alice先手为4，alice可以拿1，2。如果alice拿1，成为bob先手为3，alice赢；如果alice拿2，成为bob先手2，alice输，所以alice只会去拿1。
稍微观察一下容易发现规律(?)，alice先手为奇数时，alice必输。因为奇数的因数只有奇数，所以bob拿到的一定是一个偶数，然后bob取的时候会选择给alice一个奇数，然后一直套娃，最后肯定是alice输。当alice先手为偶数时，同理，alice会选择给bob一个奇数，然后bob就凉了(这里解释一下，因为自己为偶数时，大多数情况下可以选择给别人一个偶数，也可以选择给别人一个奇数，当然，耍赖的情况下一直取1就行了，偶数-1一定是一个奇数)。
找规律还是挺有意思的，这道题还可以用dp做，但好像没必要，就不想了。
class Solution {
public:
bool divisorGame(int N) {
return (N%2 == 0);
}
};