空气床面经 背靠背

求加米！求加米！谢谢大佬才面的没几天 挂了

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

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

贴一个第二题的代码
顺便打印一下路径~

1. def fun(l):
   
2.     l = sorted(l, key=lambda x: x[1])
   
3.     n = (l[-1][1] + 1)
   
4.     dp = [0] * n
   
5.     path = {}
   
6.     path[0] = -1
   
7.     for k, e in enumerate(l):
   
8.         interest = max(dp[e[1]], dp[e[0]] + e[2])
   
9.         for i in range(e[1], n):
   
10.             if interest > dp[i]:
    
11.                 path[interest] = k
    
12.                 dp[i] = interest
    
13. 
    
14.     ans = []
    
15.     interestMax = dp[n-1]
    
16.     while path[interestMax] != -1:
    
17.         ans.append(l[path[interestMax]])
    
18.         interestMax -= l[path[interestMax]][2]
    
19. 
    
20.     print(ans[::-1])
    
21.     return dp[n - 1]
    
22. 
    
23. 
    
24. a = [[2,4,5],[4,8,12],[10,12,4]]
    
25. print(fun(a))

复制代码

Happy-zyy 发表于 2019-10-10 15:50
贴一个第二题的代码
顺便打印一下路径~
[mw_shl_code=python,true]def fun(l):

代码第11行 path[interest] = k 这里有点不明白 如果interest是dp[e[1]] 更大的话，那就不是用的现在的e了，是不是应该加个 if dp[e[0]] + e[2] > dp[e[1]]: path[interest] = k? 已加分 求指教

zedzedQ 发表于 2019-10-12 04:07
代码第11行 path = k 这里有点不明白 如果interest是dp[e[1]] 更大的话，那就不是用的现在的e了，是不是 ...

如果interest是和dp[e[1]]相等话，是不会进去if语句的，也就是只有当dp[e[0]] + e[2] > dp[e[1]]才会执行if

Happy-zyy 发表于 2019-10-12 10:36
如果interest是和dp[e[1]]相等话，是不会进去if语句的，也就是只有当dp[e[0]] + e[2] > dp[e[1]]才会执行 ...

谢谢答疑～

最早开始 和 最晚结束的那2个 必须是在结果里面， 对吗？
这个例子， [ [2, 4, 5], [3, 5, 6], [5, 7, 10], [ 4, 8, 12], [6, 8 ,10], [10, 12, 4]]  如果我加一个 [3,11, 1000]， 结果依然还是[[2,4,5],[4,8,12],[10,12,4]]

求问面经都是在哪里找的呀

贡献一下我的解法，不知道对不对，欢迎指正。

dp[i]: 所有<=i 的情况里star最多的数量。初始化一个覆盖整个区间的dp数组。
先根据所有interval的end从小到大排序，然后遍历。很直观的 dp[end] = max(dp[end], dp[start] + star);
之后从这个interval的end1到下一个interval的end2的区间内，即[end1, end2]，dp的值都设为dp[end]

1. int maxStar(vector<vector<int>>& intervals) {
   
2.     sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[1] < b[1] || (a[1] == b[1] && a[0] < b[0]);});
   
3.     int n = intervals.back()[1];
   
4.     vector<int> dp(n+1, 0);
   
5.    
   
6.     for (int i = 0; i < intervals.size(); i++) {
   
7.         int start = intervals[i][0];
   
8.         int end = intervals[i][1];
   
9.         int star = intervals[i][2];
   
10. 
    
11.         dp[end] = max(dp[end], dp[start] + star);
    
12.         
    
13.         if (i != intervals.size() - 1) {
    
14.             for (int j = end + 1; j <= intervals[i+1][1]; j++) {
    
15.                 dp[j] = dp[end];
    
16.             }
    
17.         }
    
18.     }
    
19.    
    
20.     return dp[n];
    
21. }

复制代码

上周leetcode contest 竟然出现了这道题。。。

为什么每次我一面完 leetcode contest就有原题。。。哭哭