狗家10月底Onsite挂经

第4题可以用lis的思路来做就是nlogn了

穿袈裟的流氓 发表于 2019-1-2 05:32
第4题可以用lis的思路来做就是nlogn了

超过k的部分不要即可实现题目要求

第一题没看明白，是同一个bst相同的两个节点还是两个不同的bst的相同节点值？

第一题既然是bst可能还是加parent写比较好吧。。第四题nlogk lc 原题 - bst做

理论上你用 brute force 只要做出来了。HC也会买你的帐。无数狗家官方培训都支持只要有个可行的解法即可。不必最优。

zhangzitong001 发表于 2019-1-2 03:15
第四轮楼主应该是二分  dp 定义为长度i的increasing subsequence的最小ending值

这题长度为k-1的所有比当前值小的ending都可以用来组成长度为k的subsequence,只保存最小ending应该不行吧。。。

xil12008 发表于 2019/01/02 08:33:32


这题长度为k-1的所有比当前值小的ending都可以用来组成长度为k的subsequence,只保存最小ending应该不行吧。。。

greedy. 具体看lis的 nlogn解法.  

fengqitianlan 发表于 2019/01/02 04:39:46


不是要求最长的Sub 是要输出实际那个Sequence的具体内容

嗯嗯 可以得到最长然后找 就容易了

强制要求写Morris Traversal Iterator 有点坑啊