成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

xzavier / 1219人閱讀

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

Coins in a Line I Solution

第一個(gè)游戲者永遠(yuǎn)拿不到第3n枚硬幣，所以在硬幣總數(shù)不能被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做法，設(shè)dp[i]為第一個(gè)游戲者從第i枚硬幣到end能獲得硬幣價(jià)值的最大值。

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65486.html

相關(guān)文章

  • LintCode Coins in a line III

    摘要：復(fù)雜度思路參考的思路，對于，表示在從到的范圍內(nèi)，先手玩家能拿到的最大的硬幣價(jià)值。對于狀態(tài)，先手玩家有兩種選擇，要么拿的硬幣，要么拿的硬幣左邊一個(gè)的或者右邊一側(cè)的，如果拿左側(cè)的硬幣，如果拿右側(cè)的硬幣，取兩個(gè)值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...

    focusj 評論0 收藏0

  • Lintcode Coins in a line

    摘要：有個(gè)硬幣排成一條線。兩個(gè)參賽者輪流從右邊依次拿走或個(gè)硬幣，直到?jīng)]有硬幣為止。拿到最后一枚硬幣的人獲勝。表示的是，當(dāng)有個(gè)棋子的時(shí)候，先手玩家會不會輸。贏得條件是，和的狀態(tài)是輸?shù)臓顟B(tài)。 LintCode: coins in a line I 有 n 個(gè)硬幣排成一條線。兩個(gè)參賽者輪流從右邊依次拿走 1 或 2 個(gè)硬幣，直到?jīng)]有硬幣為止。拿到最后一枚硬幣的人獲勝。 請判定 第一個(gè)玩家 是輸還...

    itvincent 評論0 收藏0

  • Lintcode Coins in a line II

    摘要：兩個(gè)參賽者輪流從左邊依次拿走或個(gè)硬幣，直到?jīng)]有硬幣為止。計(jì)算兩個(gè)人分別拿到的硬幣總價(jià)值，價(jià)值高的人獲勝。請判定第一個(gè)玩家是輸還是贏樣例給定數(shù)組返回給定數(shù)組返回復(fù)雜度思路考慮先手玩家在狀態(tài)，表示在在第的硬幣的時(shí)候，這一位玩家能拿到的最高價(jià)值。 LintCode Coins in a line II 有 n 個(gè)不同價(jià)值的硬幣排成一條線。兩個(gè)參賽者輪流從左邊依次拿走 1 或 2 個(gè)硬幣，直...

    2shou 評論0 收藏0

  • 有多少種硬幣組合，更優(yōu)解法

    摘要：寫在前面的自我檢討上周我發(fā)布了一篇博文有多少種硬幣組合找出獨(dú)特子數(shù)組之和，是關(guān)于有多少種硬幣組合的算法題的解法。假如，現(xiàn)在我們只有一個(gè)硬幣，分。則可能性只有種，那就是。 寫在前面的自我檢討 v2 上周我發(fā)布了一篇博文有多少種硬幣組合——找出獨(dú)特子數(shù)組之和，是關(guān)于有多少種硬幣組合的算法題的解法。雖然算法本身能夠給出一個(gè)正確答案，可是仔細(xì)想來，我卻沒辦法給出一個(gè)簡單直接的解釋為什么這樣跑可...

    williamwen1986 評論0 收藏0

  • 有多少種硬幣組合——找出獨(dú)特子數(shù)組之和

    摘要：另外，我們還需要將所有硬幣組合起來，組成一個(gè)新的數(shù)組，其中包含了所有的硬幣。比如硬幣數(shù)組，和代表其數(shù)量的數(shù)組，組合成。 寫在前面的自我檢討 這道題的解法，剛開始我自己做的并不算是一個(gè)很好的解法，只能說題目是做出來了，但過程中的計(jì)算有大量的重復(fù)計(jì)算，導(dǎo)致函數(shù)復(fù)雜度直逼O(n^n)。查閱資料之后便有了一個(gè)改良版。感謝這篇文章Find all distinct subset (or subs...

    xiaoqibTn 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<