g家intern电面

bananapancake 发表于 2016-10-27 10:59
谢谢！恭喜楼主了！祝match成功！

没事！借吉言～

多谢楼主分享经验哈。第一题DP我写了一个2D版本的，就是dp[i][j]存着从i到j的最大值和最小值。能不能帮忙看一下差不多是不是这个意思哈？多谢哈

1. 
   
2. def max_subarray(nums):
   
3.     n = len(nums)
   
4.     dp = [[{"min":float("inf"), "max":-float("inf")} for i in range(n)] for j in range(n)]
   
5.     ans = -1
   
6.     for i in range(n):
   
7.         dp[i][i]["min"] = nums[i]
   
8.         dp[i][i]["max"] = nums[i]
   
9. 
   
10.     for i in range(n):
    
11.         for j in range(i+1,n):
    
12.             dp[i][j]["min"] = min(dp[i][j-1]["min"], nums[j])
    
13.             dp[i][j]["max"] = max(dp[i][j-1]["max"], nums[j])
    
14.             min_tmp = dp[i][j]["min"]
    
15.             max_tmp = dp[i][j]["max"]
    
16.             if dp[i][j]["min"] != float("inf") and min_tmp*2 > max_tmp:
    
17.                
    
18.                 ans = max(ans, j-i+1)
    
19.    
    
20.     return ans
    

复制代码

sccnju 发表于 2016-10-27 11:36
多谢楼主分享经验哈。第一题DP我写了一个2D版本的，就是dp[j]存着从i到j的最大值和最小值。能不能帮忙看一 ...

是这个意思 我看着没啥问题

williamdotyang 发表于 2016-10-27 11:52
是这个意思 我看着没啥问题

多谢哈。然后优化空间就是这二维数组里面的i其实都没有用直接去掉就行了哈？

williamdotyang 发表于 2016-10-27 10:46
min(array) 其实是等于 min(min(array), array[j]). max的情况同理。所以可以用O(1)时间填充一个二维dp m ...

但是brutal force的话难道不也是O（n^2)?

第一题，Time O(n^2), Space O(1)

1. int longest_subarray(vector<int> &nums)
   
2. {   
   
3.     int max_len = 0;
   
4. 
   
5.     int n = nums.size();
   
6. 
   
7.     for (int i = 0; i < n; i++) {
   
8.         int min_num = nums[i];
   
9.         int max_num = nums[i];
   
10. 
    
11.         for (int j = i + 1; j < n; j++) {
    
12.             min_num = min(min_num, nums[j]);
    
13.             max_num = max(max_num, nums[j]);
    
14.          
    
15.             if (min_num * 2 > max_num)
    
16.                 max_len = max(max_len, j-i+1);
    
17.         }
    
18.     }
    
19.    
    
20.     return max_len;
    
21. }
    
22. 
    
23. int main()
    
24. {   
    
25.     vector<int> nums = {1, 3, 4, 4, 3, 5, 5, 6};
    
26.    
    
27.     cout << longest_subarray(nums) << endl;
    
28. 
    
29.     return 0;
    
30. }
    

复制代码

第一题可以O(n)? 用min/max queue, 类似two poitners

1. from collections import deque
   
2. class minMaxQueue:
   
3.     def __init__(self):
   
4.         self.minq = deque()
   
5.         self.maxq = deque()
   
6.         self.q = deque()
   
7. 
   
8.     def push(self, i):
   
9.         self.q.append(i)
   
10. 
    
11.         while self.maxq and self.maxq[-1] < i:
    
12.             self.maxq.pop()
    
13.         self.maxq.append(i)
    
14. 
    
15.         while self.minq and self.minq[-1] > i:
    
16.             self.minq.pop()
    
17.         self.minq.append(i)
    
18. 
    
19.     def pop(self):
    
20.         i = self.q.popleft()
    
21. 
    
22.         if self.maxq[0] == i:
    
23.             self.maxq.popleft()
    
24. 
    
25.         if self.minq[0] == i:
    
26.             self.minq.popleft()
    
27.         return i
    
28. 
    
29.     def getMin(self):
    
30.         if self.minq:
    
31.             return self.minq[0]
    
32. 
    
33.     def getMax(self):
    
34.         if self.maxq:
    
35.             return self.maxq[0]
    
36. 
    
37. def solve(array):
    
38.     q = minMaxQueue()
    
39.     ans = 0
    
40.     for n in array:
    
41.         q.push(n)
    
42.         while q.q and q.getMin() * 2 <= q.getMax():
    
43.             q.pop()
    
44.         ans = max(ans, len(q.q))
    
45.     return ans
    

复制代码

看名字感觉好眼熟                 

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

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

楼主能具体说说第二轮吗？谢谢！