当前位置: 代码迷 >> 综合 >> js + leetcode刷题:No.1025 除数博弈
  详细解决方案

js + leetcode刷题:No.1025 除数博弈

热度:31   发布时间:2023-09-22 02:13:05.0

N%2===0?哈哈哈,还是认真写动态规划
一开始愣是做成了算数;第二眼做成了找规律,结果解法跟第一个一样;最后还是认真思考一个动态规划吧

题目:

  1. 除数博弈
    爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。

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

解法:

1、看到“最佳状态”,不就是默认正常每步都为true,那么就看最后是停留在谁那里,不是Alice则为false

// 92ms  33.7mb
var divisorGame0 = function(N) {return N%2 === 0;
}

2、第二次觉得改多列几个试试看,结果发现false、true相互交换;然后代码同上
3、后来觉得这好歹是个动态规划题,还是认真思考一下,按照题述写代码如下
(果然要快一些)

// 60ms 34.4mb
var divisorGame = function(N){if(N === 1) return falseif(N === 2) return true// 先默认全部为falselet dp = new Array(N+1).fill(false)dp[2] = true // 第二已知为truefor(let i = 3; i <= N; i++){for(let j = 1; j < i; j++){/* 判定为true的条件是:找到一个约数 且查看减去改约数后,dp[i-j] 为false 那么叠加该次,为true*/// 其实j可以为1,那么正常情况下由该规律推断,i-1前一个一定为!divisorGame(i),这也是为什么会形成规律的原因if(i%j === 0 && !dp[i-j]){dp[i] = truebreak}}}return dp[N]
}