资讯专栏INFORMATION COLUMN

5024-除数博弈

eternalshallow / 2291人阅读

摘要:前言的除数博弈爱丽丝和鲍勃一起玩游戏,他们轮流行动。只有在爱丽丝在游戏中取得胜利时才返回,否则返回。示例输入输出解释爱丽丝选择,鲍勃无法进行操作。

前言

Weekly Contest 132的 除数博弈:

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

最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作:

选出任一 x,满足 0 < x < NN % x == 0
N - x 替换黑板上的数字 N
如果玩家无法执行这些操作,就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 true,否则返回 false。假设两个玩家都以最佳状态参与游戏

示例1:

输入:2
输出:true
解释:爱丽丝选择 1,鲍勃无法进行操作。

示例2:

输入:3
输出:false
解释:爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。

提示:

1 <= N <= 1000

解题思路

本题难度为简单,可是题目的描述会感觉解题十分困难,实际上本题只需要找出爱丽丝鲍勃胜负的周期即可,同类型的题目有292. Nim游戏。下面先列出前5次的胜负情况:

N1时,由于爱丽丝先手,无法进行操作,鲍勃胜利,为false

N2时,爱丽丝胜利,为true

N3时,鲍勃胜利,为false

N4时,取数情况为1,1,1爱丽丝胜利,为true

N5时,取数情况为1,1,1,1鲍勃胜利,为false

从上面列出的胜负情况可以看出,当N奇数时,鲍勃胜利,当N偶数时,爱丽丝胜利。

实现代码
   /**
     * 5024. 除数博弈
     * 1    false
     * 2    1    true
     * 3    1    false
     * 4    1,1,1    true
     * 5    1,1,1,1   false
     * @param N
     * @return
     */
    public boolean divisorGame(int N) {
        return N%2==0;
    }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/77617.html

相关文章

  • 「leetcode」29.两数相除

    摘要:原题给定两个整数,被除数和除数。将两数相除,要求不使用乘法除法和运算符。返回被除数除以除数得到的商。右移位,等价于,除以的次方。当除以时,结果相较于除数会非常的小。我们使用循环逐渐减少右移的位数,逐渐逼近除数,当时等于,大于等于。 showImg(https://segmentfault.com/img/remote/1460000020181895); 原题 给定两个整数,被除数 d...

    googollee 评论0 收藏0
  • leetcode 29 Divide Two Integers

    摘要:很容易想到,我们每次用被除数减去除数,进行减法的次数就是最终结果。这道题的采取了一种类似二分查找的思想。除了这些,这道题还要注意一些边界情况的判断,例如除数或被除数为,值溢出等。 题目详情 Divide two integers without using multiplication, division and mod operator.If it is overflow, retu...

    马龙驹 评论0 收藏0
  • leetcode399. Evaluate Division

    摘要:题目要求已知一些字母之间的关系式,问是否能够计算出其它字母之间的倍数关系如已知问是否能够计算出的值。这里的值因为在条件中无法获知是否等于零,因此也无法计算其真实结果,也需要返回。即代表点指向点的边的权重为,而点指向点的边的全中为。 题目要求 Equations are given in the format A / B = k, where A and B are variables ...

    Jensen 评论0 收藏0
  • LeetCode29.两数相除 JavaScript

    摘要:给定两个整数,被除数和除数。将两数相除,要求不使用乘法除法和运算符。返回被除数除以除数得到的商。示例输入输出示例输入输出说明被除数和除数均为位有符号整数。假设我们的环境只能存储位有符号整数,其数值范围是。 给定两个整数,被除数 dividend和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。 返回被除数 dividend 除以除数 divisor 得到的商。...

    shiyang6017 评论0 收藏0

发表评论

0条评论

eternalshallow

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<