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

xzavier 發布于2019-08-14 15:14 / 1209人閱讀

摘要：第一個游戲者永遠拿不到第枚硬幣，所以在硬幣總數不能被整除的情況下，都可以贏。做法，設為第一個游戲者從第枚硬幣到能獲得硬幣價值的最大值。主要參考這篇文章的解釋

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];
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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