狗家昂赛

5 轮昂赛特

1 加油站问题，给你起始点A 终点B 一个数组代表每一个加油站的油价 坐标代表每一个加油站的位置 一辆车 每英里耗油V 从A出发到B最少耗油量

2 给

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

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

$
...

现在让你从城市x  到城市y  不能超过两次中转 花费的最少飞机票钱  follow up是 打印结果

wqddmh 发表于 2017-11-26 23:22
不能到就加满，然后呢？在哪里补足才是问题吧？这里我还没想明白。

第一题目前的思路是从当前加油站向后600公里（油箱支持的最大距离）寻找最低价油站，如果比当前低，就加油到开到。如果比当前高，就加满。然后下次从那个最低价油站继续这个过程。一个变量记录车上还剩多少油，一个变量记录已经花费多少钱了。
最坏情况和10楼的dp一样。平均时间好一些，因为跳过了一些站点没有算。当然复杂度还是N^2。

lyxuan1208 发表于 2018-2-19 14:20
应该是每次找600 km以内第一个比当前价格低的station? 而不是找600范围内最低？
我不太确定，怎么去一个 ...

嗯，嗯，说得有道理。
要找可行驶范围内的第一个比当前价格低的station和最低的那个station。
逻辑应该是
if exist 第一个比当前价格低的station A
  加油或者不加油，开到A
else
  加油或者不加油，开到最低的那个station
600km内，最低的station可以用维护个堆，每次把新能到达的站点塞进去，如果走了else逻辑，就把顶弹出，同时把所有已经经过的站点都弹出。
第一个比当前价格低的站点，应该也可以用上面这个堆。如果对顶比当前低，那么就顺序遍历，总能找到一个比当前低的站点。如果对顶比当前高，那么就走else逻辑。
所以逻辑重新调整下。
维护一个600km内的站点堆。
if 对顶大于当前站点
  开到对顶
else
找第一个小于当前站点的站点A
  开到A
复杂度，维护堆的操作，最坏情况就是lgn，n次，就是nlgn
if 逻辑就是nlgn
else逻辑因为每个站点在查找过程中只经历了一次，所以是n
综上复杂度是nlgn。

相跟各位讨论一下第五轮， 我也被问到过类似的题，在不知道follow up 的情况下我的做法是 BFS

keep 一个 minCost
1， 从x 出发，找到所有能一次到达的城市，如果能到y 更新minCost
2,  第一次转机：从上一层所有能到的城市再出发，找到所有能到达的城市，如果能到y 更新minCost
3，第二次转机：从上一层所有能到的城市再出发，找到所有能到达的城市，如果能到y 更新minCost
4，final：从上一层所有能到的城市再出发，找到所有能到达的城市，如果能到y 更新minCost

这道题的话三层BFS, Time O(N)

follow up 输出序列，BFS的话就不容易输出了，我的回答是DFS 或者建树来track，这样的话感觉就是另外一道题了，大家有什么好的思路吗

楼主第一题车的 1.油箱大小有限制吗？2. 是求A到B最少的价格吧。3. 如果油箱大小无限，转移方程是dp[i] = dp[k] + dist(k,i)*V*price[k]，复杂度是O(n^2). 对吗？

你第二轮的第一题和我一样，我是一个不爱说话的白人面的。但是我就这一个问题，有follow up。

第五轮只会建立graph然后DFS，有没有DP的做法？

第二题感觉和那个alien dictionary差不多

請問第一題有例子嗎? 這應該是在一條直線上的?

TrustMeBro 发表于 2017-11-25 14:07
你第二轮的第一题和我一样，我是一个不爱说话的白人面的。但是我就这一个问题，有follow up。

请问这道题的字会不会有重复的?

followup是甚么呢? 可不可以分享一下 谢谢

reliveinfire 发表于 2017-11-25 18:15
请问这道题的字会不会有重复的?

followup是甚么呢? 可不可以分享一下 谢谢

我这道题上来第一问，数组1是排好序的1-n数字，数组2是根据数组1shuffle过来，那么数组3根据一样的shuffle规则变换成数组4；第一个follow up，如果数组一是无重复数字组成的无序数组，如何做；followup2，数组数组1有重复。   这道题我一开始花了一些时间和他确认题目意思，还有后面走我写出代码跑test case，感觉题目简单了 不知道他是不是准备了2题，我太慢了。

qeroqero 发表于 2017-11-25 12:37
楼主第一题车的 1.油箱大小有限制吗？2. 是求A到B最少的价格吧。3. 如果油箱大小无限，转移方程是dp = dp[k ...

不好意思忘记说了，邮箱大小有限制。是求最少花费的价格。

wstjpu 发表于 2017-11-26 08:48
不好意思忘记说了，邮箱大小有限制。是求最少花费的价格。

感觉这样，状态转移方程还是dp[i] = dp[k] + dist(k,i)*V*price[k]，dp[i]代表到第i个加油站花费，i和k的距离最多是 max油箱/V, 对吗？ 楼主怎么做的