题目
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
链接
https://leetcode.com/problems/divisor-game/
分析
Alice and Bob 玩游戏,给定一个数字N,执行下面操作,
找到 0 < x < N and N % x == 0, N = N - 1
如果下一个人找不到x,则失败。
(1).N = 1时,Alice则输;
(2).N = 2时,Alice可以选择x = 1,N = N - 1 = 1, 则Bob输,Alice赢;
(3).N = 3时,Alice只能选择x = 1, N = N - 1 = 1, 参考(2)可知,操作2的人是赢的,则Alice输;
(4).N = 4时,Alice可选择x = 1或2,但是根据上面的经验Alice会选择x = 1, 给对方剩下数字是3,则对方输,Alice赢;
(5).N = 5时,Alice只能选择1,根据(4)则对方赢,Alice输;
输入N | Alice结果 |
---|---|
1 | False |
2 | True |
3 | False |
4 | True |
5 | False |
6 | True |
7 | False |
8 | True |
9 | False |
10 | True |
总结
偶数特点:一定可以被1和2整除;
奇数特点:一定可以被1整除,只能被奇数整除,一定不能被偶数整除;
游戏特点:最后拿到1的人则输;
因此,开始为偶数时,Alice选择减1就会给Bob的是奇数,由于奇数只能被奇数整除,故Bob减去谁,返回给Alice的只能是偶数,同理Alice还是只需要减去一个奇数返回给Bob的还是奇数,最后肯定是Bob得到1,输掉比赛;
同理,开始为奇数时,Alice操作之后给Bob的肯定是偶数,那么Bob肯定会应得比赛;
code
class Solution(object):
def divisorGame(self, N):
"""
:type N: int
:rtype: bool
"""
## 推算前面几个例子之后会发现只有给定是奇数时则输,偶数时则赢
return N%2 == 0