12.7 FB 电面 挂经

cobbjixu 发表于 2019-2-4 06:06
从前向后扫描 记录当前最小去程价钱 如果当前回程加上最小去程小于最优解 就更新最优解 从后向前扫描也可 ...

那两个数组都是已经按时间排好序的？

分享一下我的思路

一面第一题：
（这题比较像 leetcode 84 题）
新开一个list，长度和原来两个list长度相同。第i元素存储i日期及之前的去程票价最便宜的那个。O(n)时间。
再开一个list，同理，第i元素存i日期及之后回程最便宜的那个。O(n)时间。
扫描两个list。O(n) 时间。

二面第一题：
既然是double linked list 了，每个node 交换向前向后的指针就可以了。

ef50mm 发表于 2019-2-4 14:27
那两个数组都是已经按时间排好序的？

是的，a[0]表示第一天的票价，a[1]表示第二天的票价，所以位置是有用的，不能随便sort

ashun 发表于 2019-2-5 03:05
是的，a[0]表示第一天的票价，a[1]表示第二天的票价，所以位置是有用的，不能随便sort

还想再问一下如果a是去程，b是回程，可以选a[0]--b[0]或者a[1]---b[1]吗？谢谢楼主！

Hexess 发表于 2019-2-5 14:53
还想再问一下如果a是去程，b是回程，可以选a[0]--b[0]或者a[1]---b[1]吗？谢谢楼主！

呃，这个我记不太清了，好像是可以当天回程

ashun 发表于 2019-2-6 13:48
呃，这个我记不太清了，好像是可以当天回程

感谢楼主！祝楼主一切顺利！

想问下楼主，是怎么通知的挂了呢？ 直接发的邮件么，还是约了电话？～

wang513 发表于 2019-2-7 08:57
想问下楼主，是怎么通知的挂了呢？ 直接发的邮件么，还是约了电话？～

发邮件，，，，，，

饼子 发表于 2019-2-4 21:13
分享一下我的思路

一面第一题：

第一题是不是只要新开一个list存回程机票每个index右边的最小值就行啊？不需要开两个list吧