116 - 1025 除数博弈

题目

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 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

解答

又是一个。。题目都看不懂的题。

看题解，感觉类似于强20之类的的题目，只需要判断最后终局的情况即可

作者：pandawakaka 链接：https://leetcode-cn.com/problems/divisor-game/solution/python3gui-na-fa-by-pandawakaka/

简言之，最后谁先占到2谁就赢。

那么如何占到2呢？如果当前为偶数，下一个数可奇可偶；如果当前为奇数，那么下一个数只能是奇数。

因此一开始是奇数就输；是偶数就赢。

func divisorGame(N int) bool {
    return N%2 == 0
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Divisor Game.

Memory Usage: 2 MB, less than 25.00% of Go online submissions for Divisor Game.

class Solution:
    def divisorGame(self, N: int) -> bool:
        return N%2==0

Runtime: 52 ms, faster than 31.33% of Python3 online submissions for Divisor Game.

Memory Usage: 13.8 MB, less than 9.52% of Python3 online submissions for Divisor Game.

var divisorGame = function(N) {
    return N%2===0
};

Runtime: 56 ms, faster than 50.10% of JavaScript online submissions for Divisor Game.

Memory Usage: 33.8 MB, less than 40.00% of JavaScript online submissions for Divisor Game.

动态规划

https://leetcode-cn.com/problems/divisor-game/solution/fang-qi-shen-xian-jie-fa-hui-gui-pu-tong-ren-si-we/

var divisorGame = function(N) {
  let dp = []
  dp[0] = false
  dp[1] = false
  dp[2] = true
  for (let i = 3; i <= N; i++) {
    dp[i] = false
    for (let j = 1; j < i; j++) {
      if (i % j === 0 && dp[i - j] === false) {
        dp[i] = true
        break
      }
    }
  }
  return dp[N]
};

Runtime: 60 ms, faster than 28.26% of JavaScript online submissions for Divisor Game.

Memory Usage: 34.7 MB, less than 20.00% of JavaScript online submissions for Divisor Game.

func divisorGame(N int) bool {
    dp := make([]bool, N+1)
    if N > 1 {
        dp[2] = true
    }
    for i := 3; i < N+1; i++ {
        for j := 1; j < i; j++ {
            if i%j == 0 && dp[i-j] == false {
                dp[i] = true
                break
            }
        }
    }
    return dp[N]
}

Runtime: 8 ms, faster than 19.27% of Go online submissions for Divisor Game.

Memory Usage: 1.9 MB, less than 25.00% of Go online submissions for Divisor Game.

class Solution:
    def divisorGame(self, N: int) -> bool:
        dp = [False]*(N+1)
        if N > 1:
            dp[2] = False
        for i in range(N+1):
            for j in range(1, i//2+1):
                if i % j == 0 and (not dp[i-j]):
                    dp[i] = True
                    break
        return dp[N]

Runtime: 76 ms, faster than 25.31% of Python3 online submissions for Divisor Game.

Memory Usage: 13.9 MB, less than 9.52% of Python3 online submissions for Divisor Game.