狗狗跪经

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

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

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

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

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

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

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

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

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

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

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

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解法