原题
1025. Divisor Game
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number N on the chalkboard. On each player's turn, that player makes a move consisting of:
- Choosing any x with 0 < x < N and N % x == 0.
- Replacing the number N on the chalkboard with N - x.
Also, if a player cannot make a move, they lose the game.
Return True if and only if Alice wins the game, assuming both players play optimally.
Example 1:
Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.
Example 2:
Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
Note:
1 <= N <= 1000
1025. 除数博弈
Alice和Bob轮流玩一个游戏，Alice先手。
一开始，黑板上有一个数字N.在某个玩家的回合中，该玩家进行以下操作：
- 选择任意整数x，x满足0 < x < N 并且N % x == 0
- 将黑板上的数字N替换成N - x
最后，如果玩家无法选择，那么判断他游戏失败。
当且仅当Alice赢得比赛时才返回True，假设两个玩家都达到最佳状态
示例 1：
输入：2
输出：true
解释：Alice选择 1，Bob勃无法进行操作。
示例 2：
输入：3
输出：false
解释：Alice选择 1，Bob勃也选择 1，然后Alice无法进行操作。
提示：
1 <= N <= 1000
- 本题在LeetCode上在动态规划分类下
题意分析
结合LeetCode的官方分类可以猜测出本题解题思路偏向动态规划思想，动态规划的思想核心，结果之间具有互相依赖性。至少有一种思路是动态规划方向（如果了解过斐波那契数字的解法，便很容易联想到本题动态规划的具体思路。未理解过斐波那契数解法的读者请关注笔者leetcode第509题后续博文。）。另一种思路，根据题目不妨带入具体数字不难发现一个结论，偶数情况一定会赢，奇数情况一定会输。我们考虑如何证明这个结论。
方法一：动态规划
思路:
当N为1：
无数字x可带入，输
当N为2：
带入数字x=1能赢。
当N为3：
若x为1，对手回合新N为2，根据上述推导结论N为2时对手赢，而自己输，继续尝试改变x
若x为2，无法整除舍弃
当N为4：
若x为1，对手回合新N为3，根据上述推导结论N为3时对手输，而自己赢，无需继续尝试改变x；
伪代码：
1、声明一个大小为N+1的boolean数组，用于存取从1～N每个数组对应输赢，数组下标表示数组，值表示输赢（初始win[1]默认为输）
2、双重循环遍历：
第一层循环从数字2到数组N循环遍历，按照从小到大；
第二层循环从1到当前外层循环数组x（不包含x），按照从小到大；
i.n % x ==0 能整除时，判定对手的下一回合win[n-x]输赢，若对手输则自然当前回合能赢，将结果赢存入数组win[n]
ii.否则，x自增后继续尝试i；
3、遍历结束从2到N的输赢结果均保留在数组中，返回win[N]；
- 注意：
动态规划整体上提交结果正确，但是也由于循环次数较多，在时间空间复杂度等效率方面并不高。实际项目需结合具体场景进行算法选型
动态规划实现代码：
public boolean divisorGame(int N) {
boolean[] win = new boolean[N + 1];
for (int n = 2; n <= N; ++n) {
for (int x = 1; x < n; x++) {
if (n % x == 0) {
if (!win[n - x]) {
win[n] = true;
break;
}
}
}
}
return win[N];
}
方法二：根据奇偶规律证明
思路:
当N为1：赢
当N为2：赢
当N为3：输
当N为4：赢
...
发现规律N为奇数赢，N为偶数输，则转化为数学问题证明题。
证明：
一、N为奇数时
1.N为质数，则x必然只能为1，则对手回合N变成 N - 1 为数字更小的偶数；
2.N不为质数，存在x，则x必然为奇数，对手回合N变成 N - x 为数字更小的偶数；
结论：N为奇数时，对手回合必然为偶数且N减小。
二、N为偶数时我方赢
证明：
1.令x等于1，对手回合N变成 N - 1 为数字更小的奇数；
2.对手回合的N必然为奇数，由一可知操作后我方的N必然为减小的偶数，我方持续令x=1；
3.最终回合对手N减小为1，对手输而我方赢；
结论：N为偶数时我方赢。
二、N为奇数时我方输
证明：
1.N为质数，则x必然只能为1，而对手回合则变成偶数，由一可知，对手令x=1对手赢，我方输；
2.N不为质数，存在x，则x必然为奇数，对手回合N变成 N - x 为数字更小的偶数，由一可知，对手令x=1对手赢，我方输；
结论：N为奇数时我方输。
实现代码：
public boolean divisorGame(int N) {
return (N & 1) == 0;
}
彩蛋
仔细观察第二种方法实现的时候，并不是使用N % 2 == 0来判断奇偶，而是通过(N & 1) == 0来判断，这便是本文的彩蛋。千里之行，始于足下，共勉之～
扫一扫 关注我的微信订阅号
网友评论