SnapChat 电面挂经

很nice的国人小哥，说不定他能看到这里，haha

不知道是不是leetcode原题，我没见到过，求见过的给个link
题目：A跟B在play game，从int[]里拿数字
A：拿第一个/最后

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

谢谢他（如果他看到的话）

反正呢就是没有写出来，因为智商是无法逾越的鸿沟啊。。最后祝大家offer多多！

谢谢楼主分享。我也说一下我的想法。

假设输入为Array nums，如果我们定义Max(i, j)为A能从nums的i到j子序列中能拿到的最大和的话。那么，
(1) Max(i, j) = nums[i], if i == j;
(2) Max(i, j) = Math.max(nums[i], nums[j]), if j - i = 1;
这两个是base cases
(3) 然后如果 j - i > 1, 那么我们就比较拿第一个nums[i]好，还是最后一个nums[j]好：
     1. 假如拿nums[i], Max(i, j)’ = nums[i] + (nums[i+1] > nums[j] ? Max(i+2, j) : Max(i+1, j-1)) // 括号里面决定B拿剩下的第一个还是最后一个。
     2. 假如拿nums[j], Max(i, j)’’ = nums[j] + (nums[i] > nums[j-1] ? Max(i+1, j-1) : Max(i, j-2)).
所以Max(i, j) = Math.max(Max(i, j)’, Max(i, j)’’)
最后return Max（0，nums.length - 1).

因为j 是大于等于i的，所以我们只用了dp table的右上部分。从对角线开始，以与对角线垂直方向，一步一步向右上方增加。
dp代码：

public static int maxSumOfA(int[] nums){

                int dp[][] = new int[nums.length][nums.length];

                for(int i = 0; i < nums.length; i++){

                        dp[i][i] = nums[i];

                }

                for(int i = 0; i < nums.length - 1; i++){

                        dp[i][i+1] = Math.max(nums[i], nums[i+1]);

                }

                int j = 2;

                while(j < nums.length){

                        for(int i = 0; i < nums.length - j; i++){

                                int takeFirst = nums[i] + (nums[i+1] > nums[i+j] ? dp[i+2][i+j] : dp[i+1][i+j-1]);

                                int takeLast = nums[i+j] + (nums[i] > nums[i+j-1] ? dp[i+1][j-1] : dp[i][j-2]);

                                dp[i][j+i] = Math.max(takeFirst, takeLast);

                        }

                        j++;

                }

                return dp[0][nums.length - 1];

        }

补充内容 (2016-4-21 10:23):
(1) Max(i, j) = nums[i], if i == j;
(2) Max(i, j) = Math.max(nums[i], nums[j]), if j - i = 1;

补充内容 (2016-4-21 10:23):
nums【i】显示不出来。。

1. class Solution {
   
2.   public static void main(String[] args) {
   
3.     int[] nums = {3,7,2,1};
   
4.     int max = dp(nums);
   
5.     System.out.println(max);
   
6.   }
   
7.   public static int dp(int[] nums) {
   
8.     int size = nums.length;
   
9.     int[][] dp = new int[size][size];
   
10.     //----gap----//
    
11.     for(int i = 0; i < size; ++i) {
    
12.       dp[i][i] = nums[i];
    
13.     }
    
14.     for(int i = 0; i+1 < size; ++i) {
    
15.       dp[i][i+1] = Math.max(nums[i], nums[i+1]);
    
16.     }
    
17.     for(int i = 2; i < size; ++i) {
    
18.       //left bound
    
19.       for(int j = 0; j+i < size; ++j) {
    
20.         int one = nums[j]+(nums[j+1] < nums[j+i]?dp[j+1][j+i-1]:dp[j+2][j+i]);
    
21.         int two = nums[j+i]+(nums[j] < nums[j+i-1]?dp[j][i+j-2]:dp[j+1][j+i-1]);
    
22.         dp[j][i+j] = Math.max(one, two);
    
23.       }
    
24.     }
    
25.     return dp[0][size-1];
    
26.   }
    
27. }
    

复制代码

补充内容 (2016-4-19 07:02):
感觉最近都是这种路数..........

补充内容 (2016-4-19 11:12):
要不要去投下snapchat.....

满城尽带黄金甲 发表于 2016-9-5 02:21
有个问题，如果是[5, 7, 8, 5]这个subarray， B先拿，那么它会拿哪个？如果B拿第一个5，那么A可以在剩下的 ...

你考虑的这个跟我想法一样, 所以我对上面的解法有一些疑问.

我觉得如果轮到B取的时候, 如果coin[i] == coin[j], 此时我们不能默认B就取 i 或 j (上面的解法把== 归到了> or < 的情况, 我觉得是不对的), 而是我们应该假定B取得结果使得A剩余的能取得的最大值最小.

个人解法:

1. public static int takeMost(int[] coins){
   
2.                 int n = coins.length;
   
3.                 int[][] dp = new int[n+2][n+2];
   
4.                 for(int j=0; j<n; j++){
   
5.                         for(int i=j; i>=0; i--){
   
6.                                 if(i >= j-1){
   
7.                                         dp[i][j] = Math.max(coins[i], coins[j]);
   
8.                                 } else{         // <----  i <= j - 2
   
9.                                         // A takes coins[i]
   
10.                                         int opt1 = coins[i];
    
11.                                         if(coins[i+1] > coins[j]){
    
12.                                                 opt1 += dp[i+2][j];
    
13.                                         } else if (coins[i+1] < coins[j]){
    
14.                                                 opt1 += dp[i+1][j-1];
    
15.                                         } else{
    
16.                                                 opt1 += Math.min(dp[i+2][j], dp[i+1][j-1]);
    
17.                                         }
    
18.                                         // A takes coins[j]
    
19.                                         int opt2 = coins[j];
    
20.                                         if(coins[i] > coins[j-1]){
    
21.                                                 opt2 += dp[i+1][j-1];
    
22.                                         } else if(coins[i] < coins[j-1]){
    
23.                                                 opt2 += dp[i][j-2];
    
24.                                         } else {
    
25.                                                 opt2 += Math.min(dp[i][j-2], dp[i+1][j-1]);
    
26.                                         }
    
27.                                         dp[i][j] = Math.max(opt1, opt2);                                               
    
28.                                 }                                       
    
29.                         }
    
30.                 }
    
31.                 return dp[0][n-1];
    
32.         }

复制代码

coins in a line, leetcode

补充内容 (2016-4-19 06:37):
sorry, Lintcode   Coins in a LineII

ykwwind 发表于 2016-4-19 07:01
补充内容 (2016-4-19 07:02):
感觉最近都是这种路数..........

赞！谢谢层主

newbiee 发表于 2016-4-19 06:36
coins in a line, leetcode

补充内容 (2016-4-19 06:37):

是很像，谢谢～～

这题有点意思。还有个变种，就是B也用最优策略（和A一样），想尽一切办法拿到最大的数字。问先手的A能拿到多少。

ruochenzhang 发表于 2016-4-19 07:41
是很像，谢谢～～

不太一样。Coins in a line只能从一头拿，所以是个一维的DP问题。这个题可以从两头拿，就变成二维的了。

这题思想感觉跟他家前段时间考的那个minimum palindrome edit distance有点相似啊

写了个recursive的，你们看下吧

1. import java.io.*;
   
2. import java.util.*;
   
3. 
   
4. public class Solution{
   
5.    
   
6.     public static void main(String[] args){
   
7.         int[] nums = {3,7,2,1};
   
8.         int start = 0;
   
9.         int end = nums.length-1;
   
10.         System.out.println(Math.max(helper(1, nums, start, end),helper(2, nums, start, end)));
    
11.     }
    
12.    
    
13.     public static int helper(int flag, int[] nums, int start, int end){
    
14.         if(start>end) return 0;
    
15.         
    
16.         int sum = 0;
    
17.         if(flag==1){
    
18.             sum = nums[start];
    
19.             start++;
    
20.         }else{
    
21.             sum = nums[end];
    
22.             end--;
    
23.         }
    
24.         
    
25.         if(nums[start]<nums[end])end--;
    
26.         else start++;
    
27.         
    
28.         return Math.max(helper(1, nums, start, end),helper(2, nums, start, end))+sum;
    
29.         
    
30.     }
    
31. }

复制代码