LintCode Coins in a line III

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

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

LintCode Coins in a line III

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.
Could you please decide the first player will win or lose?
Example
Given array A = [3,2,2], return true.
Given array A = [1,2,4], return true.
Given array A = [1,20,4], return false.

Recursion + Memorization

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

思路
參考coins II的思路，對于dpi，表示在從i到j的范圍內，先手玩家能拿到的最大的硬幣價值。
對于狀態(tài)dpi，先手玩家有兩種選擇，要么拿num[i]的硬幣，要么拿num[j]的硬幣(左邊一個的或者右邊一側的），
如果拿左側的硬幣，dpi = num[i] + sumi + 1 - dpi + 1
如果拿右側的硬幣，dpi = num[j] + sumi - dpi
取兩個值的最大值。

也可以用dp寫。

for(int k = 2; k < len; k ++) {
    for(int i = 0; i < len - k; i ++) {
        int right = i + k;
        dp[i][right] = Math.max();
    }
}

代碼

int len;
Map map = new HashMap<>();

public boolean coins(int[] num) {
    len = num.length;
    int[] sum = new int[len];
    for(int i = 0; i < len; i ++) {
        if(i == 0) sum[i] = num[i];
        else sum[i] = num[i] + sum[i - 1];
    }
    return helper(num, 0, len - 1, sum) * 2 > sum[len - 1];
}

public int helper(int[] num, int left, int right, int[] sum) {
    // base case;
    if(left > right) return 0;
    if(left == right) return num[left];
    if(map.containsKey(left * len + right)) return map.get(left * left + right);
    //
    int val = Math.max(num[left] + getSum(left + 1, right, sum) - helper(num, left + 1, right, sum), num[right] + getSum(left, right - 1, sum) - helper(num, left, right - 1, sum));
    map.put(left * len + right, val);
    return val;
}

GPU云服務器云服務器 Coins LintCode III LintCode134_LRU

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

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/65256.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

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

itvincent 2019-08-14 15:03 評論0 收藏0
Lintcode Coins in a line II

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

2shou 2019-08-14 15:03 評論0 收藏0
[LintCode/LeetCode] House Robber III

摘要：解法真的非常巧妙，不過這道題里仍要注意兩個細節(jié)。中，為時，返回長度為的空數組建立結果數組時，是包括根節(jié)點的情況，是不包含根節(jié)點的情況。而非按左右子樹來進行劃分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...

macg0406 2019-08-14 15:34 評論0 收藏0
[LintCode] Majority Number I II III

摘要：遍歷整個數組，用一個計數器，找出超過整個數組長度二分之一的那個數。規(guī)則是當前數等于，計數器加否則，計數器減。當的大小等于時，統(tǒng)計中所有的，并將所有對應的減，若被減為，就從中移除這對鍵值。 Majority Number I Problem Given an array of integers, the majority number is the number that occurs ...

sPeng 2019-08-14 15:43 評論0 收藏0