狗狗19summer欧诶新题

倒序浏览 · 2018-10-10 13:31:28

室友昨天做了oa还是旧题，今天打开一看第一题是新题，能碰上题库更新我也是很“幸运”。。。。拿到题第一时间有点懵，看懂了之后还好，毕竟我是用暴力解法做出来的。。。

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

第二题还是原题，stores和house找最近的商店。
分享一下，攒攒人品，希望能拿到更多的OA和店面。

jarjingx668 · 2018-10-11 04:29:14

第一题就反过来存，存每个点的孩子，然后从根开始dfs，手动用栈记一下当前在递归里的点，然后每个点返回当前栈倒数第D的就好了吧，这样整体复杂度是线性的，比暴力更好打

shimmer422 · 2018-10-10 14:11:25

第一题的暴力解应该是一层一层往上找直到得到-1或者层数达到D吧。
我的想法是可以用一个二维数组ancestors[A.length][D + 1] 来保存每个node的第几个ancestor防止重复计算来优化

匿名用户-WHBEN *2018-10-11 01:51:45* · 2018-10-11 01:51:45

shimmer422 发表于 2018-10-10 14:11
第一题的暴力解应该是一层一层往上找直到得到-1或者层数达到D吧。
我的想法是可以用一个二维数组ancestors ...

有点类似于DP的思想？把之前的都保存下来？

xuhang57 · 2018-10-11 02:58:23

楼主有想到什么edge/corner cases么？

匿名用户-WHBEN *2018-10-11 03:41:53* · 2018-10-11 03:41:53

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

OJASHAHAHA · 2018-10-11 14:33:19

shimmer422 发表于 2018-10-9 22:11
第一题的暴力解应该是一层一层往上找直到得到-1或者层数达到D吧。
我的想法是可以用一个二维数组ancestors ...

所以暴力解法时间是O(D*N) 空间O(1)

然后2D ancestors解法时间是O(N) 空间是O(D*N)l咯？

Gareth_Yao · 2018-12-19 09:00:37

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