184. 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

链接

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
上一篇:TCP和TLS/SSL会话细节


下一篇:区块链隐私保护:Grin 中的交易详解