12.7 FB 电面挂经

ashun

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

12月面了两轮技术电面
第一轮，1，给两个List，一个表示去程的票价，一个表示回程的票价，index是对应日期，求最小的往返程的票价总和。注意，回程

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

，有原题，不是很难，感觉也做出来了差不多，但是挂了，，，，

求大米！！

饼子

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

ef50mm

Hexess 发表于 2019-2-4 01:59
求问一下dp O(N)的做法，谢谢！

同问不是先要排序么？

ashun

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

pengdu

是不是交流问题？

第一题是从后往前找，每次都放到一个bst，然后找lower bound，nlogn的复杂度。

cobbjixu

第一题第一问DP O(n)可解第二问每个元素value都不一样吗？

Hexess

cobbjixu 发表于 2019-2-4 00:10
第一题第一问DP O(n)可解第二问每个元素value都不一样吗？

求问一下dp O(N)的做法，谢谢！

cobbjixu

Hexess 发表于 2019/02/04 01:59:49

求问一下dp O(N)的做法，谢谢！

从前向后扫描记录当前最小去程价钱如果当前回程加上最小去程小于最优解就更新最优解从后向前扫描也可以记录最小回程就行了

ashun

cobbjixu 发表于 2019-2-4 00:10
第一题第一问DP O(n)可解第二问每个元素value都不一样吗？

value值好像是不一样的，但其实这个值没有用，只是用来标记不同节点吧

ashun

ef50mm 发表于 2019-2-4 02:08
同问不是先要排序么？

我第一个的做法就是倒着找，因为只返回最低的票价是多少，不用管日期，所以只要有一个res记录全程中的最小值即可

pengdu

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

12.7 FB 电面 挂经