狗家昂赛

请问LZ面试的时候都是单刀直入直接算法题么？ 还是会问一些bq或者基础知识题？ lz有没有考系统设计啊？

qeroqero 发表于 2017-11-26 11:01
感觉这样，状态转移方程还是dp = dp[k] + dist(k,i)*V*price[k]，dp代表到第i个加油站花费，i和k的距离最 ...

我觉得第一题 可以直接 找当前站 之后油费比它少的站，然后看当前加满油 是否能到，不能到 就加满，能到就加到正好到的程度，然后一直遍历每个站 用这个方法，感觉是O(n^2) 复杂度好高

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

如果油箱大小无限制。那么只要不断更新最低油价的站点就可以了吧，复杂度应该是O(n)。
如果油箱有限制该怎么做？

hychin 发表于 2017-11-25 16:26
第五轮只会建立graph然后DFS，有没有DP的做法？

图上两点最短距离那个算法dij？

lxc0694 发表于 2017-11-26 12:52
我觉得第一题 可以直接 找当前站 之后油费比它少的站，然后看当前加满油 是否能到，不能到 就加满，能到 ...

不能到就加满，然后呢？在哪里补足才是问题吧？这里我还没想明白。

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

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

wqddmh 发表于 2017-11-26 23:46
第一题目前的思路是从当前加油站向后600公里（油箱支持的最大距离）寻找最低价油站，如果比当前低，就加 ...

可以维护一个向后600公里的最低价格站点序列，每次到一个新位置，直接取最小值就好。那么复杂度降为nlogn

wqddmh 发表于 2017-11-26 23:46
第一题目前的思路是从当前加油站向后600公里（油箱支持的最大距离）寻找最低价油站，如果比当前低，就加 ...

好厉害,想了一会儿没有想到反例.
大概的正确性可以这么说明:
假设最优路线不是停在我们指定的这个最低价油站,那么一定在最低价油站的之前或之后需要停留一次.
1.如果最优路线停留点在最低价油站之后,我们完全可以先到最低价油站,再到这个最优路线上停留点,那么最优路线不是最优,自相矛盾.
2.如果最优路线停留点在最低价油站之前,我们完全可以先到最低价油站,再到下一个最优路线停留点,这样也可以推翻最优路线,使其自相矛盾.
所以最优路线停留点就在局部的最低价油站.

相跟各位讨论一下第五轮， 我也被问到过类似的题，在不知道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，这样的话感觉就是另外一道题了，大家有什么好的思路吗

xGuo 发表于 2017-11-30 23:48
相跟各位讨论一下第五轮， 我也被问到过类似的题，在不知道follow up 的情况下我的做法是 BFS

keep 一个 ...

第五轮dp吧：
dp[i][j], i表示转机次数，可以是0, 1, 2   j表示到达的地点, 可以是a, b, c
所以dp[i][j] = min (dp[i - 1][k] + price[k][j]) k表示所有可以到达的地点, 可以是a, b, c
最后max(dp[0][y], dp[1][y], dp[2][y]) 就是结果

补充内容 (2017-12-4 09:14):
论坛的bug？第一个个方括号自动消失？重写下
dp(i, j), i表示转机次数，可以是0, 1, 2   j表示到达的地点, 可以是a, b, c
所以dp(i, j) = min (dp[i - 1][k] + price[k][j]) k表示所有可以到达的地点, 可以是a, b...