Google二跪

刚刚结束的谷歌电面,已经妥妥地感觉到了凉意。二跪谷歌,哎

一道DP的题目。玩卡牌,N张卡,卡上有数字,可正可负。两个玩家,每个人最多可以选1,2或3张牌,自己先开始,问最多能获得的分数是多少,score就是player选择的卡上数字之和。

感觉还是自己学艺不精吧,之前挂过一次谷歌,再面试,心理状态很爆炸。感觉小哥最后的good luck特别无。哎,move on吧

补充内容 (2018-9-8 05:58):

原来乐扣有相似的题目(热心小伙伴回复:464,486,877),评论的小伙伴都特别厉害,祝大家找工作顺利!(没错,我发了两遍,第一次用补充功能。。)欢迎小伙伴一起探讨[刷题]良策!

写了个解题报告,大家讨论一下。

玩卡牌,N张卡,卡上有数字,可正可负。两个玩家,每个人最多可以选1,2或3张牌,自己先开始,问最多能获得的分数是多少?

题目解析:

两个玩家A和B,每个人每次可以选择1,2或3张牌。从A玩家开始,目标是消耗完所有卡牌A能获取的最大分数。首先明确一个原则,任何一个玩家在选择卡牌时,目标都是要获取最大的分数。 所以任何玩家面对任意多张卡牌时的目标都是获取最大分数。即A先选,A会计算面对剩余的i张卡牌取1,2或者3张获得最大分数。轮到B选择时,B会计算面对剩余的A取之后的卡牌取1,2或者3张怎么获得最大分数。

基本思路:

基于以上的分析,我们可以知道,A面对n张卡片获取的最大分数与B面对n-1张卡片获取的最大分数,B面对n-2张卡片获取的最大分数和B面对n-3张卡片获取的最大分数有关。什么关系呢?具体推倒如下,我们定义A面对n张卡片获取的最大分数为dp[A][n].上面的关系即可以表达为dp[A][n]取决于dp[A][n-1], dp[A][n-2]和dp[B][n-3]。到底dp[A][n]如何表达呢?
如果A选择1张卡牌,dp[A][n] = sum(n-1) - dp[B][n-1] + cards[0]
如果A选择2张卡牌,dp[A][n] = sum(n-2) - dp[B][n-2] + cards[0] + card[1]
如果A选择3张卡牌,dp[A][n] = sum(n-3) - dp[B][n-3] + cards[0] + card[1] + card[2]

根据题目要求取以上三种情况下的最大值.

我们发现 sum(n-1) + cards[0] = sum(n-2) + cards[0] + cards[1] = sum(n-3) + cards[0] + cards[1] + cards[2] = sum(n). 所以dp[A][n] = max(sum[n] - dp[B][n-1], sum[n] - dp[B][n-2], sum[n] - dp[B][n-3]); 或者说 dp[A][n] = sum[n] - min(dp[B][n-1], dp[B][n-2], dp[B][n-3]);

因此我们可以写出以下代码

class Solution {
    int maxScore(int[] cards) {
        int n = cards.length;
        int[][] dp = new int[2][n + 1];
        int sum = 0;
        int A, B;
        A = 0; B = 1;

        for (int i = 1; i <= n; i++) {
            // sum is the score sum of left i cards
            sum += cards[n - i];

            for (int j = 0; j < 2; j++) {
                int min = Integer.MAX_VALUE;
                if (i >= 3) min = Math.min(min, dp[B][i - 3]);
                if (i >= 2) min = Math.min(min, dp[B][i - 2]);
                if (i >= 1) min = Math.min(min, dp[B][i - 1]);
                dp[A][i] = sum - min;

                A = (A + 1) % 2;
                B = (B + 1) % 2;
            }

        }

        return dp[0][n];
    }
}

优化1:

手动跑cards[] = {1, 2, -3, 8}; 我们发现其实dp[A]和dp[B]是完全相同的。因为dp[A][n]意味A先选和dp[B][n]意味着B先选。A和B的位置可以互选且对称的。因此我们可以仅仅定义一维数组dp[n]. dp[n]表示玩家面对n张卡牌获取的最大分数。

代码优化为

class Solution {
    int maxScore(int[] cards) {
        int n = cards.length;
        int[] dp = new int[n + 1];
        int sum = 0;

        for (int i = 1; i <= n; i++) {
            sum += cards[n - i];

            int min = Integer.MAX_VALUE;
            if (i >= 3) min = Math.min(min, dp[i - 3]);
            if (i >= 2) min = Math.min(min, dp[i - 2]);
            if (i >= 1) min = Math.min(min, dp[i - 1]);

            dp[i] = sum - min;
        }

        return dp[n];
    }
}

优化2:

再次审视代码,dp[n]只与dp[n-1],dp[n-2]和dp[n-3]有关,我们甚至不需要一维数组,三个变量即可。

class Solution {
    int maxScore(int[] cards) {
        int n = cards.length;
        int p, q, r, sum;

        p = q = Integer.MAX_VALUE;

        // init when no card
        r = sum = 0;

        for (int i = 1; i <= n; i++) {
            sum += cards[n - i];

            int min = Math.min(Math.min(p, q), r);
            p = q;
            q = r;
            r = sum - min;
        }

        return r;
    }
}

写了个recursive版本的

[Java] 纯文本查看 复制代码
public int findMaxScore(int[] cards) {
int[] memo = new int[cards.length];
int sum = 0;
for (int card: cards) sum += card;
return (sum + helper(cards, 0, memo)) / 2;
}

public int helper(int[] cards, int cur, int[] memo) {
    if (cur == cards.length - 1) return cards[cur];
    if (cur == cards.length - 2) return Math.max(cards[cur] - cards[cur + 1], cards[cur] + cards[cur + 1]);
    if (cur == cards.length - 3) {
        int valOne = cards[cur] - Math.max(cards[cur + 1] - cards[cur + 2], cards[cur + 1] + cards[cur + 2]);
        int valTwo = cards[cur] + cards[cur + 1] - cards[cur + 2];
        int valThree = cards[cur] + cards[cur + 1] + cards[cur + 2];
        return Math.max(valOne, Math.max(valTwo, valThree));
    }
    if (memo[cur] > 0) return memo[cur];
    int oneCardValue = cards[cur] - helper(cards, cur + 1, memo);
    int twoCardValue = cards[cur] + cards[cur + 1] - helper(cards, cur + 2, memo);
    int threeCardValue = cards[cur] + cards[cur + 1] + cards[cur + 2] - helper(cards, cur + 3, memo);
    memo[cur] = Math.max(oneCardValue, Math.max(twoCardValue, threeCardValue));
    return memo[cur];
}

贴一个DP的解法,如有问题还请指正。
[C++] 纯文本查看 复制代码#include

bool solution(vectornums)
{
int N = nums.size();
vectorsum(N+1);
sum[N] = 0;
for (int i=N-1; i>=0; i–)
sum[i] = sum[i+1]+nums[i];

vector<int>dp(N+1,0);
dp[N-1]=sum[N-1];
dp[N-2]=max(sum[N-2],nums[N-2]);

for (int i=N-3; i>=0; i--)
{
    int scoreA = nums[i]+sum[i+1]-dp[i+1];
    int scoreB = nums[i]+nums[i+1]+sum[i+2]-dp[i+2];
    int scoreC = nums[i]+nums[i+1]+nums[i+2]+sum[i+3]-dp[i+3];
    dp[i] = max(scoreA,scoreB);
    dp[i] = max(dp[i],scoreC);
}
return dp[0]>=sum[0]-dp[0];        

}

int main()
{
vectornums({1,2,-3,8});
cout<<solution(nums)<<endl;
}

写了个解题报告,大家讨论一下。

题目解析:

两个玩家A和B,每个人每次可以选择1,2或3张牌。从A玩家开始,目标是消耗完所有卡牌A能获取的最大分数。首先明确一个原则,任何一个玩家在选择卡牌时,目标都是要获取最大的分数。 所以任何玩家面对任意多张卡牌时的目标都是获取最大分数。即A先选,A会计算面对剩余的i张卡牌取1,2或者3张获得最大分数。轮到B选择时,B会计算面对剩余的A取之后的卡牌取1,2或者3张怎么获得最大分数。

基本思路:

基于以上的分析,我们可以知道,A面对n张卡片获取的最大分数与B面对n-1张卡片获取的最大分数,B面对n-2张卡片获取的最大分数和B面对n-3张卡片获取的最大分数有关。什么关系呢?具体推倒如下,我们定义A面对n张卡片获取的最大分数为dp[A][n].上面的关系即可以表达为dp[A][n]取决于dp[A][n-1], dp[A][n-2]和dp[B][n-3]。到底dp[A][n]如何表达呢?
如果A选择1张卡牌,dp[A][n] = sum(n-1) - dp[B][n-1] + cards[0]
如果A选择2张卡牌,dp[A][n] = sum(n-2) - dp[B][n-2] + cards[0] + card[1]
如果A选择3张卡牌,dp[A][n] = sum(n-3) - dp[B][n-3] + cards[0] + card[1] + card[2]

根据题目要求取以上三种情况下的最大值.

我们发现 sum(n-1) + cards[0] = sum(n-2) + cards[0] + cards[1] = sum(n-3) + cards[0] + cards[1] + cards[2] = sum(n). 所以dp[A][n] = max(sum[n] - dp[B][n-1], sum[n] - dp[B][n-2], sum[n] - dp[B][n-3]); 或者说 dp[A][n] = sum[n] - min(dp[B][n-1], dp[B][n-2], dp[B][n-3]);

因此我们可以写出以下代码

class Solution {
    int maxScore(int[] cards) {
        int n = cards.length;
        int[][] dp = new int[2][n + 1];
        int sum = 0;
        int A, B;
        A = 0; B = 1;

        for (int i = 1; i <= n; i++) {
            // sum is the score sum of left i cards
            sum += cards[n - i];

            for (int j = 0; j < 2; j++) {
                int min = Integer.MAX_VALUE;
                if (i >= 3) min = Math.min(min, dp[B][i - 3]);
                if (i >= 2) min = Math.min(min, dp[B][i - 2]);
                if (i >= 1) min = Math.min(min, dp[B][i - 1]);
                dp[A][i] = sum - min;

                A = (A + 1) % 2;
                B = (B + 1) % 2;
            }

        }

        return dp[0][n];
    }
}

优化1:

手动跑cards[] = {1, 2, -3, 8}; 我们发现其实dp[A]和dp[B]是完全相同的。因为dp[A][n]意味A先选和dp[B][n]意味着B先选。A和B的位置可以互选且对称的。因此我们可以仅仅定义一维数组dp[n]. dp[n]表示玩家面对n张卡牌获取的最大分数。

代码优化为

class Solution {
    int maxScore(int[] cards) {
        int n = cards.length;
        int[] dp = new int[n + 1];
        int sum = 0;

        for (int i = 1; i <= n; i++) {
            sum += cards[n - i];

            int min = Integer.MAX_VALUE;
            if (i >= 3) min = Math.min(min, dp[i - 3]);
            if (i >= 2) min = Math.min(min, dp[i - 2]);
            if (i >= 1) min = Math.min(min, dp[i - 1]);

            dp[i] = sum - min;
        }

        return dp[n];
    }
}

优化2:

再次审视代码,dp[n]只与dp[n-1],dp[n-2]和dp[n-3]有关,我们甚至不需要一维数组,三个变量即可。

class Solution {
    int maxScore(int[] cards) {
        int n = cards.length;
        int p, q, r, sum;

        p = q = Integer.MAX_VALUE;

        // init when no card
        r = sum = 0;

        for (int i = 1; i <= n; i++) {
            sum += cards[n - i];

            int min = Math.min(Math.min(p, q), r);
            p = q;
            q = r;
            r = sum - min;
        }

        return r;
    }
}

LC 464
LC 486
LC 877

这拿牌有顺序的吧,只能从两边拿吗,还是只能从头到尾按照顺序拿?

从头到尾按顺序拿

按顺序拿?能跳牌吗?两个人必须间隔吗?

跟从两头拿思路应该是一样的[Java] 纯文本查看 复制代码拿一张 = sum[i + 1][j] - dp[i + 1][j] + nums[i]
拿二张 = sum[i + 2][j] - dp[i + 2][j] + nums[i] + nums[i + 1]
拿三张 = sum[i + 3][j] - dp[i + 3][j] + nums[i] + nums[i + 1] + nums[i + 2]
dp[i][j] = max(拿一张, 拿二张, 拿三张)

对,按顺序拿,不能跳牌,两个人轮流来

麻烦问一下,这题是地里面经题么?我之前面经看很少。感谢感谢!

leetcode上有个很类似的题是每次从两头拿看谁能赢

请问是每人每次可以选1到3张,直到最后选完么?