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

xzavier 发布于2019-08-14 15:14 / 1211人阅读

摘要：第一个游戏者永远拿不到第枚硬币，所以在硬币总数不能被整除的情况下，都可以赢。做法，设为第一个游戏者从第枚硬币到能获得硬币价值的最大值。主要参考这篇文章的解释

Coins in a Line I Solution

第一个游戏者永远拿不到第3n枚硬币，所以在硬币总数不能被3整除的情况下，都可以赢。

public class Solution {
    public boolean firstWillWin(int n) {
        return n % 3 != 0; 
    }
}

Coins in a Line II Problem

There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.

Could you please decide the first player will win or lose?

Example

Given values array A = [1,2,2], return true.

Given A = [1,2,4], return false.

Note

DP做法，设dp[i]为第一个游戏者从第i枚硬币到end能获得硬币价值的最大值。

Solution

Fool Lintcode method: it happened to work! But it"s completely wrong!

public class Solution {
    public boolean firstWillWin(int[] A) {
        // write your code here
        if (A == null) return false;
        int sum = 0;
        for (int i = 1; i <= A.length / 3; i++) {
            sum += A[3*i-1];
        }
        int total = 0;
        for (int i = 0; i < A.length; i++) {
            total += A[i];
        }
        if (sum * 2 > total) return false;
        return true;
    }
}

DP method

主要参考这篇文章的解释

http://www.mamicode.com/info-...

public class Solution {
    public boolean firstWillWin(int[] values) {
        // write your code here
        int len = values.length;
        if (len <= 2) {
            return true;
        }
        //dp[i] means the largest value you(the first player) 
        //can get when you start from values[i] 
        int[] dp = new int[len+1];
        //not even exist
        dp[len] = 0;
        //when you happen to have the last coin, yes, consider the last first
        dp[len-1] = values[len-1];
        //sure we should get the last two for most value
        dp[len-2] = values[len-1] + values[len-2];
        //same rules, why leave two(len-1, len-2) for the other player
        dp[len-3] = values[len-2] + values[len-3];
        //next we are gonna sum up
        for (int i = len-4; i >= 0; i--) {
            //you have to have values[i] and the non-optimal later choice
            //because the other player is smart to leave you the worse one
            //between two of your optimal choices
            dp[i] = values[i] + Math.min(dp[i+2], dp[i+3]);
            dp[i] = Math.max(dp[i], values[i] + values[i+1] + Math.min(dp[i+3], dp[i+4]));
            //equals to: dp[i] = Math.max(values[i] + Math.min(dp[i+2],dp[i+3]), values[i] + values[i+1] + Math.min(dp[i+3], dp[i+4]));
        }
        //compute the total value of coins
        int sum = 0;
        for (int a: values) {
            sum += a;   
        }
        //compare your final value to the other player"s
        return dp[0] > sum - dp[0];
    }
}

Now let"s make the code elegant

public class Solution {
    public boolean firstWillWin(int[] values) {
        if (values == null || values.length == 0) return false;
        int n = values.length;
        if (n < 3) return true;
        int[] dp = new int[n+1];
        dp[n] = 0;
        dp[n-1] = values[n-1];
        dp[n-2] = values[n-1]+values[n-2];
        dp[n-3] = values[n-2]+values[n-3];
        for (int i = n-4; i >= 0; i--) {
            dp[i] = Math.max(values[i] + Math.min(dp[i+2], dp[i+3]), values[i] + values[i+1] + Math.min(dp[i+3], dp[i+4]));
        }
        int sum = 0;
        for (int v: values) sum += v;
        return dp[0] > sum - dp[0];
    }
}

GPU云服务器云服务器 Coins line line 245 line连我

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

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

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

摘要：有个硬币排成一条线。两个参赛者轮流从右边依次拿走或个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。表示的是，当有个棋子的时候，先手玩家会不会输。赢得条件是，和的状态是输的状态。 LintCode: coins in a line I 有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。请判定第一个玩家是输还...

itvincent 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