Lintcode Coins in a line

itvincent 发布于2019-08-14 15:03 / 3098人阅读

摘要：有个硬币排成一条线。两个参赛者轮流从右边依次拿走或个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。表示的是，当有个棋子的时候，先手玩家会不会输。赢得条件是，和的状态是输的状态。

LintCode: coins in a line I

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

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

n = 1, 返回 true.
n = 2, 返回 true.
n = 3, 返回 false.
n = 4, 返回 true.
n = 5, 返回 true.

复杂度
O(N),O(N)

思路
最少是n = 3时，返回false，说明当一个player面临只有3个棋子的时候，他肯定会输。
dp[i]表示的是，当有i个棋子的时候，先手玩家会不会输。dp[i]这个状态可以由dp[i - 1]或者dp[i - 2]跳过来。dp[i]赢得条件是，dp[i - 1]和dp[i - 2]的状态是输的状态。

可以优化空间复杂度到O(1)。

代码

public boolean firstWillWin(int n) {
    boolean[] dp = new boolean[n + 1];
    for(int i = 1; i <= n; i ++) {
        if(i == 1 || i == 2) dp[i] = true;
        else dp[i] = !dp[i - 1] || !dp[i - 2];
    }
    return dp[n];
}

GPU服务器服务器托管 Coins LintCode LintCode134_LRU Lines

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

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

[LintCode] Coins in a Line I & Coins in a Line

摘要：第一个游戏者永远拿不到第枚硬币，所以在硬币总数不能被整除的情况下，都可以赢。做法，设为第一个游戏者从第枚硬币到能获得硬币价值的最大值。主要参考这篇文章的解释 Coins in a Line I Solution 第一个游戏者永远拿不到第3n枚硬币，所以在硬币总数不能被3整除的情况下，都可以赢。 public class Solution { public boolean fi...

xzavier 2019-08-14 15:14 评论0 收藏0
LintCode Coins in a line III

摘要：复杂度思路参考的思路，对于，表示在从到的范围内，先手玩家能拿到的最大的硬币价值。对于状态，先手玩家有两种选择，要么拿的硬币，要么拿的硬币左边一个的或者右边一侧的，如果拿左侧的硬币，如果拿右侧的硬币，取两个值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...

focusj 2019-08-14 15:03 评论0 收藏0
Lintcode Coins in a line II

摘要：两个参赛者轮流从左边依次拿走或个硬币，直到没有硬币为止。计算两个人分别拿到的硬币总价值，价值高的人获胜。请判定第一个玩家是输还是赢样例给定数组返回给定数组返回复杂度思路考虑先手玩家在状态，表示在在第的硬币的时候，这一位玩家能拿到的最高价值。 LintCode Coins in a line II 有 n 个不同价值的硬币排成一条线。两个参赛者轮流从左边依次拿走 1 或 2 个硬币，直...

2shou 2019-08-14 15:03 评论0 收藏0
有多少种硬币组合，更优解法

摘要：写在前面的自我检讨上周我发布了一篇博文有多少种硬币组合找出独特子数组之和，是关于有多少种硬币组合的算法题的解法。假如，现在我们只有一个硬币，分。则可能性只有种，那就是。写在前面的自我检讨 v2 上周我发布了一篇博文有多少种硬币组合——找出独特子数组之和，是关于有多少种硬币组合的算法题的解法。虽然算法本身能够给出一个正确答案，可是仔细想来，我却没办法给出一个简单直接的解释为什么这样跑可...

williamwen1986 2019-08-23 12:52 评论0 收藏0
有多少种硬币组合——找出独特子数组之和

摘要：另外，我们还需要将所有硬币组合起来，组成一个新的数组，其中包含了所有的硬币。比如硬币数组，和代表其数量的数组，组合成。写在前面的自我检讨这道题的解法，刚开始我自己做的并不算是一个很好的解法，只能说题目是做出来了，但过程中的计算有大量的重复计算，导致函数复杂度直逼O(n^n)。查阅资料之后便有了一个改良版。感谢这篇文章Find all distinct subset (or subs...

xiaoqibTn 2019-08-23 12:34 评论0 收藏0