Lintcode Coins in a line

itvincent 發(fā)布于2019-08-14 15:03 / 3312人閱讀

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

LintCode: coins in a line I

有 n 個硬幣排成一條線。兩個參賽者輪流從右邊依次拿走 1 或 2 個硬幣，直到?jīng)]有硬幣為止。拿到最后一枚硬幣的人獲勝。

請判定第一個玩家是輸還是贏？

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

復(fù)雜度
O(N),O(N)

思路
最少是n = 3時，返回false，說明當(dāng)一個player面臨只有3個棋子的時候，他肯定會輸。
dp[i]表示的是，當(dāng)有i個棋子的時候，先手玩家會不會輸。dp[i]這個狀態(tài)可以由dp[i - 1]或者dp[i - 2]跳過來。dp[i]贏得條件是，dp[i - 1]和dp[i - 2]的狀態(tài)是輸?shù)臓顟B(tài)。

可以優(yōu)化空間復(fù)雜度到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云服務(wù)器云服務(wù)器 Coins LintCode LintCode134_LRU Lines

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

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

相關(guān)文章

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

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

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

摘要：復(fù)雜度思路參考的思路，對于，表示在從到的范圍內(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 2019-08-14 15:03 評論0 收藏0
Lintcode Coins in a line II

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

2shou 2019-08-14 15:03 評論0 收藏0
有多少種硬幣組合，更優(yōu)解法

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

williamwen1986 2019-08-23 12:52 評論0 收藏0
有多少種硬幣組合——找出獨特子數(shù)組之和

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

xiaoqibTn 2019-08-23 12:34 評論0 收藏0