亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

xzavier / 1270人閱讀

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

Coins in a Line I Solution

第一個游戲者永遠拿不到第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]為第一個游戲者從第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];
    }
}

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

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

相關(guān)文章

  • LintCode Coins in a line III

    摘要：復雜度思路參考的思路，對于，表示在從到的范圍內(nèi)，先手玩家能拿到的最大的硬幣價值。對于狀態(tài)，先手玩家有兩種選擇，要么拿的硬幣，要么拿的硬幣左邊一個的或者右邊一側(cè)的，如果拿左側(cè)的硬幣，如果拿右側(cè)的硬幣，取兩個值的最大值。 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

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

    itvincent 評論0 收藏0

  • Lintcode Coins in a line II

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

    2shou 評論0 收藏0

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

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

    williamwen1986 評論0 收藏0

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

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

    xiaoqibTn 評論0 收藏0

發(fā)表評論

0條評論

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