做网站的必要,网络营销运营公司,建设南大街小学网站,网站开发和维护1025 除数游戏
小艾 和 小鲍 轮流玩游戏#xff0c;小艾首先开始。 最初#xff0c;黑板上有一个数字 n 。在每个玩家的回合中#xff0c;该玩家做出的动作包括#xff1a;
选择任意 x#xff0c;使 0 x n 和 n % x 0 。将黑板上的数字 n 替换为 n - x 。 此…1025 除数游戏
小艾 和 小鲍 轮流玩游戏小艾首先开始。 最初黑板上有一个数字 n 。在每个玩家的回合中该玩家做出的动作包括
选择任意 x使 0 x n 和 n % x 0 。将黑板上的数字 n 替换为 n - x 。 此外如果玩家无法采取行动他们就会输掉比赛。
当且仅当 小艾赢得游戏时返回 true 假设两个玩家都发挥最佳。
例子 在大学某个自习的下午小白坐在教室看到这道题。想想现年景一过没有什么理由再不学习了。真是若对黄花孤负酒怕黄花也笑人岑寂。
这时候黑长直女神过来问小白你看到1025这道题了吗怎么感觉看着很简单但是理解起来很麻烦啊这道题你有什么思路呢
小白内心镇定这机会不就来了吗小美《一起摇太阳》有机会一起去看看吧 哦不是题目描述意思说的简单一些。
这种题目我们首先把他进行下条件梳理
从这个问题来看小艾可以从 1 to N 中选择一个数字并且她必须选择优化她的获胜。同样小鲍也会努力为自己赢得胜利。
考虑如果数字是 2 小艾以 1 开头并且她赢了
对于 3 小艾选择 1 小鲍再次选择 1 小艾输了
咱们拿4举个例子
4 小艾 - (4 - 1) - 剩下 3 给 小鲍 3 小鲍 - (3 -1) - 剩下 2 给 小艾 2 小艾 - (2 - 1) - 剩下 1 给 小鲍
现在鲍勃无法选择任何东西他输了
像这样如果我们尝试每个数字我们将得到一个模式如果我们知道 N 是奇数那么 小艾输了如果 N 是偶数小艾赢了。
解决这个问题的简单方法是返回 N % 2 0
小白没问题谁叫为了“真爱”呢。
真正面试环节
面试官咱们今天来个轻松的你可以解答这道”除数游戏“的题目吗来看看你对简单题目的理解。
小白嘿嘿这不巧了么这不是。
public boolean divisorGame(int N) {return N % 2 0;}小明OK完事儿等着面试官来表扬自己吧。他肯定会说小子你是个好手工位都给你准备好了工资你说了算。
面试官矮油不错啊不过你是不是完成的太快了这么一行就像糊弄我。是否还有其他办法呢。 小明OS今年这个找工市场人言洛阳花似锦偏我来时不逢春。。。不是谁让你这出题正好有简单方法呢
public static boolean divisorGame(int N) {// dp数组dp[i]表示Ni时小艾是否能获胜boolean[] dp new boolean[N 1];for (int i 2; i N; i) {// 对于每个N遍历所有可能的选择for (int x 1; x i; x) {if (i % x 0 !dp[i - x]) {dp[i] true;break;}}}return dp[N];}小白您好面试官这回可以了吧我终于有钱请小美看电影了 更多算法题解请看 面试数据结构与算法总结分类leetcode目录【基础版】 编码道路漫漫只要先看脚下的路徐徐前进即可。
