Uber L5a 店面挂经

最近越面越差，现在店面已经过不了了，面到了一道没见过的题目。
We have a freight train that services stations on a rail line. The train makes stops at these stations to load and unload packages.

Every day each station indicates the packages available for the train to pickup and the packages it can receive from the train.

When the train makes a sto

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

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

ion(zero indexed)   1   2   4   5
Drop                    0   1   4   7   ->  Max total deliveries = 12
Pickup                  6   1   5   0
Loads Onboard the train 6   6   7   0

感觉有点像利口 1235，当时现场没做出来。。。
如果觉得有帮助，请大家加点大米，感谢！

这jb题目跟个小作文似的

最近正好在刷题，随便写了个python dp的解。 准确性和效率我都没怎么测，只是给大家提供点思路

1. dp={}
   
2. def helper(index,load):
   
3.    
   
4.     if index in dp and load<=dp[index][0]:
   
5.         return min(load,dp[index][1])
   
6.    
   
7.     if index>=len(triplets):
   
8.         return 0
   
9.     pickup,drop,skip=triplets[index]
   
10.     pick_up_skip=index+max(1+skip,1)
    
11. 
    
12.     result=max(helper(index+1,load),min(drop,load)+helper(pick_up_skip,load-min(drop,load)+pickup))
    
13.     dp[index]=(load,result)
    
14.     return result
    
15. def solution():
    
16.     return helper(0,0)

复制代码

LZ加油！主要是最近形势不好，祝早日拿offer!

topdown dp + memorizaiton 感觉可以解，或者从后向前的bottom up dp?
感觉有点像复杂版本的house robber

axel981109 发表于 2022-8-25 03:30
最近正好在刷题，随便写了个python dp的解。 准确性和效率我都没怎么测，只是给大家提供点思路

测试了一下您的解法，拿楼主的例子，应该是12，但是这个解法好像是return了11。麻烦大佬帮忙优化一下，在准备电面，怕遇到这道就跪了

匿名用户 发表于 2022-8-30 18:16
测试了一下您的解法，拿楼主的例子，应该是12，但是这个解法好像是return了11。麻烦大佬帮忙优化一下，在 ...

这个题我也写了一下，代码其实很短，但复杂度不低：没发现简单的贪心思路， 所以要穷举所有可能性。

1. def max_transaction(station_stripets):
   
2.         mem = {}
   
3.         def helper(i, curr):
   
4.                 if (i, curr) in mem:
   
5.                         return mem[(i, curr)]
   
6.                 if i>=len(station_stripets):
   
7.                         return 0
   
8.                 pick, receive, skip =  station_stripets[i]
   
9.                 ret = max(helper(i+1, curr), helper(i+1+skip, max(0, curr-receive)+pick)+min(curr, receive))
   
10.                 mem[(i, curr)]=ret
    
11.                 return ret
    
12.         return helper(0, 0)
    
13. 
    
14. station_stripets = [[4,0,2], [6,2,0], [1,1,0], [4,4,1], [5,4,0], [4,10,0]]
    
15. print(max_transaction(station_stripets))

复制代码

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

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