建设网站合同,手机做wordpress,黑马程序员前端培训费用,做国际网站阿里巴巴1. 题目
爱丽丝和鲍勃一起玩游戏#xff0c;他们轮流行动。爱丽丝先手开局。
最初#xff0c;黑板上有一个数字 N 。在每个玩家的回合#xff0c;玩家需要执行以下操作#xff1a;
选出任一 x#xff0c;满足 0 x N 且 N % x 0 。用 N - x 替换黑板上的数字…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来源力扣LeetCode 链接https://leetcode-cn.com/problems/divisor-game 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目
LeetCode 810. 黑板异或游戏博弈推理 LeetCode 5447. 石子游戏 IV hard博弈DP
如果N是奇数奇数的约数只能是奇数奇数减去奇数偶数 拿到奇数偶数再-1有为奇数拿到奇数必输如果N是偶数我每次减1让对方是奇数必赢
class Solution {
public:bool divisorGame(int N) {//return N%2 0;return (N1)0;}
};0 ms 6 MB 动态规划
win[n] 表示剩余数字是 n 的时候胜算 true or false
class Solution { //C
public:bool divisorGame(int N) {if(N 1)return false;vectorbool win(N1,false);win[1] false;win[2] true;for(int Ni 3, x; Ni N; Ni){ //当前数字 Nifor(x 1; x Ni; x){ //我可以取小于 Ni 的 x留给对手的数字是 Ni-xif(Ni%x 0 win[Ni-x]false)//x可以取且 留给对手的数使其失败win[Ni] true;//那我就赢了哈哈}}return win[N];}
};12 ms 6.1 MB
class Solution: # py3def divisorGame(self, N: int) - bool:if N 1:return Falsedp [False]*(N1)dp[1] Falsedp[2] Truefor i in range(1, N1):for j in range(1, i):if i%j 0 and not dp[i-j]:dp[i] Truereturn dp[N]我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
