美文网首页
LintCode394 硬币排成线

LintCode394 硬币排成线

作者: 留十夜 | 来源:发表于2017-05-10 14:57 被阅读0次

问题:

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬币的人获胜。

请判定 第一个玩家 是输还是赢?

样例
n = 1, 返回 true.

n = 2, 返回 true.

n = 3, 返回 false.

n = 4, 返回 true.

n = 5, 返回 true.

分析:

  • 隐含假设二人都是高手,都会尽可能采取最优策略让自己获胜
  • 从后向前分析,即最后剩多少硬币时第一个人可以获胜?一定是3个。因此逐渐递推,只要是3个一组,对方先取,就一定获胜。
  • 唯一坏的情况就是n是3的倍数。

代码:

bool firstWillWin(int n) {
        // write your code here
        return n%3;
    }

只有一行,竟还是中等难度。

相关文章

  • LintCode394 硬币排成线

    问题: 有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚...

  • LintCode 硬币排成线

    有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬币的人...

  • 394. 硬币排成线

    描述 有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬...

  • 394. 硬币排成线

    描述 有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬...

  • 396. 硬币排成线 III

    描述 有 个硬币排成一条线, 第 枚硬币的价值为 .两个参赛者轮流从任意一边取一枚硬币, 直到没有硬币为止. ...

  • 拿硬币

    有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬币的人...

  • Java 算法-硬币排成线II(动态规划)

      好久没有做面试题了,感觉自己的编程能力又变弱了。  今天在lintCode上做了一道题,关于动态规划,比较有意...

  • 盲人道 2020-9-19

    今天上学的路上,我看到我们上学的路上有黄色的排成一条线的东西。这条线我以前总是爱踩着这条线走。可是这条线到...

  • Lintcode394 Coins in a Line so

    【题目描述】 There are n coins in a line. Two players take turn...

  • 软件开发团队玩翻硬币游戏 v0.2

    我把5张餐桌摆成一条线,然后拿着那20枚硬币坐到最外面的桌子旁,对开发团队众人说:“咱们现在玩翻硬币游戏啦。我需要...

网友评论

      本文标题:LintCode394 硬币排成线

      本文链接:https://www.haomeiwen.com/subject/jmhgtxtx.html