宽禁带半导体 pandas Egret Engine vue表单 郑州网站开发 matlab对数函数 ab软启动器 mysql汉化包 mysql新建数据库 destoon模板 react python3删除文件 python命令行 python包 python使用正则表达式 java集合框架 java求和 java写文件 java语言代码大全 java匿名对象 java数组添加值 java实现队列 java数组 java安装教程 java获取本机ip h5模板 pushstate 销售单软件 51脚本 php取整函数 生存猎人属性 魔兽改图工具 思源字体 0x00000057 字符串分割成数组 vue定时器 autocad2004迷你版 语音转文字转换器 camworks 追评可以删除吗
当前位置: 首页 > 学习教程  > 编程语言

leetcode【每日一题】1025. 除数博弈 Java

2020/7/24 9:07:28 文章标签:

题干

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

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

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

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

示例 1:

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

示例 2:

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

想法

递推
Alice 处在 N = kN=k 的状态时,他(她)做一步操作,必然使得 Bob 处于 N = m (m < k)N=m(m<k) 的状态。因此我们只要看是否存在一个 m 是必败的状态,那么 Alice 直接执行对应的操作让当前的数字变成 m,Alice 就必胜了,如果没有任何一个是必败的状态的话,说明 Alice 无论怎么进行操作,最后都会让 Bob 处于必胜的状态,此时 Alice 是必败的。

结合以上我们定义 f[i] 表示当前数字 i 的时候先手是处于必胜态还是必败态。

Java代码

class Solution {
    public boolean divisorGame(int N) {
        boolean[] f = new boolean[N + 5];

        f[1] = false;
        f[2] = true;
        for (int i = 3; i <= N; ++i) {
            for (int j = 1; j < i; ++j) {
                if ((i % j) == 0 && !f[i - j]) {
                    f[i] = true;
                    break;
                }
            }
        }

        return f[N];
    }
}

今天思路代码都参考官方题解


本文链接: http://www.dtmao.cc/news_show_50004.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?