1025. 除数博弈
Difficulty: 简单
爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。
最初,黑板上有一个数字 N
。在每个玩家的回合,玩家需要执行以下操作:
- 选出任一
x
,满足0 < x < N
且N % x == 0
。 - 用
N - x
替换黑板上的数字N
。
如果玩家无法执行这些操作,就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True
,否则返回 false
。假设两个玩家都以最佳状态参与游戏。
示例 1:
输入:2
输出:true
解释:爱丽丝选择 1,鲍勃无法进行操作。
示例 2:
输入:3
输出:false
解释:爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。
提示:
1 <= N <= 1000
Solution
这是一个博弈题目。解答此题目,首先要明确Alice(简称A)的获胜条件,就是要给对手留下奇数,最终使得A的N=2,此时A取1,B就输掉了。因此,**A先手,当N为偶数时,A必赢,反之必输。**具体原理是:
- 奇数的任何约数都是奇数,奇数减去奇数一定是偶数,因此A遇到奇数时无法给对方留下奇数,A输;
- 偶数减去奇数一定是奇数,因此A遇到偶数可以直接减去1,保证对方是奇数。到最后A必然是2,此时取1的话,A赢。
代码就一行。
class Solution {
public boolean divisorGame(int N) {
return N%2 == 0 ? true : false;
}
}
原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/tech/aiops/1298.html