狗狗跪经

周四电面了google，不出意料的跪了。互相介绍，然后google doc上开始做题：
第一题:

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

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

真心不会，求地里各路大神指导指导。
哎，啥也别说接着刷题去了。。。

假设 dp(nums, i, j)表示从index i开始，到index j 结束（两边都包括）的能拿到的最大值， sum(nums, i, j) 表示从i到j的和 (可以用presum求)
那么 dp(nums, i, j) = max( nums[i]+sum(nums, i+1, j) - dp(nums, i+1, j),     nums[j]+sum(nums, i, j-1) - dp(nums, i, j-1)) 分别表示我取第一个或者最后一个之后，对方也选取子问题最优解，那么我能拿到的就是sum-dp
出口是i==j的时候， 返回nums[i],  i>j自然就返回0啦
中间结果用二维数组存一下避免重复计算
最后问题求解的就是dp(nums, 0, len-1)吧
请指正
另外我一直在想这个问题数学上也没有办法用类似于奇偶性什么来求。。

第二题大概思路应该是dfs+memo数组吧，感觉是minimax问题，对方拿的少，自己才能拿的多

deepcopy其实就是每次都重新create一个list node，大概就是LinkedNode(originalNode.val)就算是deep copy了吧？

第二题就是DP的做法~摸摸头~

# Definition for a binary tree node.
class LinkedNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None



class Solution:
    """
    @param root: a TreeNode, the root of the binary tree
    @return: nothing
    """

    def deepcopyLinked(self, root):
        head = LinkedNode(0)
        
        while root:
            head.next = LinkedNode(root.val)
            root = root.next
        
        return head.next

bambloo 发表于 2018-4-22 07:46
第二题大概思路应该是dfs+memo数组吧，感觉是minimax问题，对方拿的少，自己才能拿的多

不用memo就是DP

第二题类似莉蔻斯巴溜吧

好像是四八六

1. class Solution {
   
2. public:
   
3.     map<pair<int,int>, pair<int,int> > cache;
   
4.     bool PredictTheWinner(vector<int>& nums) {
   
5.         pair<int,int> res = helper(nums, 0, nums.size()-1);
   
6.         return res.first >= res.second; // 这里改成return res.first即为第一个人能拿到的最大钱数
   
7. 
   
8.     }
   
9.     pair<int,int> helper(vector<int> & nums, int l, int r){
   
10.         pair<int,int> cur(l,r);
    
11.         if(cache.count(cur)) return cache[cur];
    
12.         int x = (nums.size() - (r-l))%2 , y = (x+1)%2;
    
13.         if(l==r){
    
14.             cache[cur] = pair<int,int>(nums[l]*x, nums[l]*y);
    
15.             return cache[cur];
    
16.         }
    
17.         if(x){ // A pick
    
18.             pair<int,int> res1 = helper(nums, l+1, r);
    
19.             res1.first += nums[l];
    
20.             pair<int,int> res2 = helper(nums, l, r-1);
    
21.             res2.first += nums[r];
    
22.             cache[cur] = res1.first>res2.first ? res1 : res2;
    
23.         }
    
24.         else{
    
25.             pair<int,int> res1 = helper(nums, l+1, r);
    
26.             res1.second += nums[l];
    
27.             pair<int,int> res2 = helper(nums, l, r-1);
    
28.             res2.second += nums[r];
    
29.             cache[cur] = res1.second>res2.second ? res1 : res2;
    
30.         }
    
31.         return cache[cur];
    
32.     };
    
33. };

复制代码

LC思霸留，只是return的内容不一样，原题是判断A是否能赢，DP + cache解法