Lintcode Coins in a line

itvincent 發布于2019-08-14 15:03 / 3288人閱讀

摘要：有個硬幣排成一條線。兩個參賽者輪流從右邊依次拿走或個硬幣，直到沒有硬幣為止。拿到最后一枚硬幣的人獲勝。表示的是，當有個棋子的時候，先手玩家會不會輸。贏得條件是，和的狀態是輸的狀態。

LintCode: coins in a line I

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

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

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

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

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

可以優化空間復雜度到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云服務器云服務器 Coins LintCode LintCode134_LRU Lines

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65260.html

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

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

xzavier 2019-08-14 15:14 評論0 收藏0
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 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