电面 爱比

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

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

iriswei 发表于 2019-9-23 06:56
马上要面abb了，求群主指点下，拜托了🙏

看最新的回复

楼主我真的是把能加米都给你了，**逼只能每次+1
谢谢谢谢！

一个带记忆的dfs的做法，先把所有experiences 按照end time排序dp(k,duration), 代表从前k个里选若干experience, 这些experience在duration (in hours) 范围内，欢迎一起讨论。

1. 
   
2. #include<bits/stdc++.h>
   
3. using namespace std;
   
4. class Solution {
   
5. public:
   
6.     vector<vector<int>> memo;
   
7.     int dp(vector<vector<int>>& experiences,int k,int duration){
   
8.         int start = experiences[k][0];
   
9.         int end = experiences[k][1];
   
10.         int interest = experiences[k][2];
    
11.         if(k==0) {
    
12.             if(end-start<=duration) return interest;
    
13.             return 0;
    
14.         }
    
15.         if(duration<=0) return 0;
    
16.         if(memo[k][duration]) return memo[k][duration];
    
17.         memo[k][duration] = dp(experiences,k-1,duration);
    
18.         if(end-start<=duration) {
    
19.             memo[k][duration] = max(memo[k][duration],interest);
    
20.             for(int i = k-1;i>=0;i--){
    
21.                 if(experiences[i][1]<=start){
    
22.                     memo[k][duration] = max(memo[k][duration],interest+dp(experiences,i,duration-(end-experiences[i][1])));
    
23.                 }
    
24.             }
    
25.         }
    
26.         return memo[k][duration];
    
27.     }
    
28.     static bool comp(vector<int>& a,vector<int>&b){
    
29.         return a[2]<b[2];
    
30.     }
    
31.     int maxInterest(vector<vector<int>> experiences){
    
32.         // sort experience by end date in ascending order
    
33.         sort(experiences.begin(),experiences.end(),comp);
    
34.         int n = experiences.size();
    
35.         memo.resize(n,vector<int>(25,0));
    
36.         return dp(experiences,n-1,24);
    
37.     }
    
38. };
    
39. 
    
40. int main(){
    
41.     Solution s;
    
42.     vector<vector<int>> experiences({{0,5,5},{6,8,12},{0,3,1}});
    
43.     cout<<s.maxInterest(experiences);
    
44. }   

复制代码

徐小桃 发表于 2019-9-23 07:10
时间有点久了但我记得我是这样做的
dp代表的是在时间i时能选的最大interest数 因为是1天的时间所以可以a ...

时间复杂不是nlogn吗因为得用sort？请问是怎么做到n的啊

zhimingli123 发表于 2019/09/23 12:50:59
时间复杂不是nlogn吗因为得用sort？请问是怎么做到n的啊

不算sort的话 因为之前那个人说是n方 这里只是解释一下不是n方

楼主店面大概多久又回复的呀

HanBurger 发表于 2019-9-24 06:47
楼主店面大概多久又回复的呀

他们家 我大概都是等了2到3个工作日才有消息的

贴一下自己的代码，但这个时间复杂度是O（nk)，其中n是item数量，k是最大时间

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 = [-1] * n
   
6.     for k,e in enumerate(l):
   
7.         interest = max(dp[e[1]], dp[e[0]] + e[2])
   
8.         for i in range(e[1],n):
   
9.             if interest > dp[i]:
   
10.                 path[i] = k
    
11.                 dp[i] = interest
    
12. 
    
13.     ans = []
    
14.     j = n - 1
    
15.     while path[j] != -1:
    
16.         ans.append(l[path[j]])
    
17.         j = dp[j-l[path[j]][2]]
    
18. 
    
19.     print(ans)
    
20.     return dp[n-1]
    
21. 
    
22. 
    
23. a = [[6, 18, 2],[0, 3, 1], [0, 5, 5]]
    
24. print(fun(a))
    
25. 
    
26. 
    
27. #[[0, 5, 5], [6, 18, 2]]
    
28. #7
    

复制代码

感觉这一题也好像可以不sort直接用map存(endTime, indexes of experiences ending at endTime) 然后再traverse 0 - 23 每个check一下map然后update dp[i]的最大interest, 这样的话times是O(n) (存map用n, traverse update dp是O(1)) 不过就是用了个extra space