Hudson River Trading OA

Holycarota · 2021-10-16 14:38:13

总体不难，第二题DP做的O(n^2) 结果最

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

strong>
C++的OA

无名棋脚 · 2021-10-16 21:19:02

第二题我猜是做最长不减子序列，然后用全长减子序列长再减一就是答案。复杂nlogn

Holycarota · 2021-10-17 00:59:27

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

小亩_7eb2878 · 2021-10-20 06:57:03

第二题用贪心法可以做到n*log(n)复杂度，问题等价于找最长上升子序列。只要定义一个greedy list，然后loop i到n，list里面的第k个元素表示当前数组前i个数中，长度为k的上升子列最后一个数的最小值。list是递增序列，所以loop里每次更新只需要log(n)复杂度。

Abby_Mo · 2021-10-16 20:39:41

请问楼主是几点收到的邀请链接呀?我没收到，spam里也没有，有点慌

Abby_Mo · 2021-10-16 20:40:06

还有这个是换到hankrank了嘛？之前看好像都是codility

avocado77 · 2021-10-16 21:05:33

同问是换到hackerrank了吗？

Abby_Mo · 2021-10-16 21:10:05

本帖最后由 Abby_Mo 于 2021-10-16 09:11 编辑

avocado77 发表于 2021-10-16 09:05
同问是换到hackerrank了吗？

朋友，请问你是收到链接了嘛？他的邮件里说是12:00am，是凌晨吧？还是说美东中午收到啊

avocado77 · 2021-10-16 22:02:06

本帖最后由 avocado77 于 2021-10-16 10:06 编辑

无名棋脚发表于 2021-10-16 09:19
第二题我猜是做最长不减子序列，然后用全长减子序列长再减一就是答案。复杂nlogn

你的子序列指的是连续的吗

avocado77 · 2021-10-16 22:02:31

Abby_Mo 发表于 2021-10-16 09:10
朋友，请问你是收到链接了嘛？他的邮件里说是12:00am，是凌晨吧？还是说美东中午收到啊

我是美东凌晨收到的

Abby_Mo · 2021-10-16 22:06:26

avocado77 发表于 2021-10-16 07:02:31
我是美东凌晨收到的

啊，谢谢。。。也是3小时的吗？

无名棋脚 · 2021-10-16 22:14:43

avocado77 发表于 2021-10-16 10:02
你的子序列指的是连续的吗

不连续，参考力扣300