LintCode Coins in a line III

focusj 发布于2019-08-14 15:03 / 1157人阅读

摘要：复杂度思路参考的思路，对于，表示在从到的范围内，先手玩家能拿到的最大的硬币价值。对于状态，先手玩家有两种选择，要么拿的硬币，要么拿的硬币左边一个的或者右边一侧的，如果拿左侧的硬币，如果拿右侧的硬币，取两个值的最大值。

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的范围内，先手玩家能拿到的最大的硬币价值。
对于状态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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.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

摘要：有个硬币排成一条线。两个参赛者轮流从右边依次拿走或个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。表示的是，当有个棋子的时候，先手玩家会不会输。赢得条件是，和的状态是输的状态。 LintCode: coins in a line I 有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。请判定第一个玩家是输还...

itvincent 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
[LintCode/LeetCode] House Robber III

摘要：解法真的非常巧妙，不过这道题里仍要注意两个细节。中，为时，返回长度为的空数组建立结果数组时，是包括根节点的情况，是不包含根节点的情况。而非按左右子树来进行划分的。 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

摘要：遍历整个数组，用一个计数器，找出超过整个数组长度二分之一的那个数。规则是当前数等于，计数器加否则，计数器减。当的大小等于时，统计中所有的，并将所有对应的减，若被减为，就从中移除这对键值。 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