狗家 Intern 十月九新OA

z920631580 · 2018-10-10 11:39:12

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

x

刚做完的OA，两道题，一道新题第一题给一个数组表示树节点的par

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

是store&house，地里有

sunneet · 2018-10-12 23:56:55

如果先花 O(n) 把節點建成圖
然後對圖 DFS 的時候，一邊維護一個存 path 的 queue 且長度最多為D
queue 超過長度 D 就表示 queue 的front 是距離你D的parent
這樣應該可以 O(n) 做掉?

manyfun711 · 2018-10-13 06:12:38

O(n)的时间复杂度，O(n)的空间复杂度，用一个数组记录当前位置遍历的路径方向，然后判断深度，如果深度大于D则引入新的指针沿着同样的路径遍历，即为解。

z920631580 · 2018-10-12 23:27:08

Darkneece 发表于 2018-10-11 21:38
请问楼主 dp怎么解？只想到暴力解法

我觉得暴力应该是标答，dp我想到的是先build tree，然后对树dp，做post order traversal，每个node的D ancestor是它孩子的D ancestor的ancestor。如果D很大的话这样会快一些感觉
nvm。。。如果遇到了直接写暴力吧

louiseruiwenli · 2018-10-11 14:32:28

用DP的方法好像是N * N吧？暴力解也只有N * D, 这两种方法完全depend on N和D的数量。

Darkneece · 2018-10-11 21:38:26

请问楼主 dp怎么解？只想到暴力解法

z920631580 · 2018-10-12 23:29:57

louiseruiwenli 发表于 2018-10-11 14:32
用DP的方法好像是N * N吧？暴力解也只有N * D, 这两种方法完全depend on N和D的数量。

好像也是D*N。。。。。一个树的leaf最多是N/2嘛。。。
nvm。。。我在对着空气优化了。。。。

Austintutu · 2018-10-12 23:34:38

louiseruiwenli 发表于 2018-10-11 14:32
用DP的方法好像是N * N吧？暴力解也只有N * D, 这两种方法完全depend on N和D的数量。

Re你的这个算法，这个还是要看树的层数大小。n层,一个n*n的二维数组即可。

21212131 · 2018-10-14 17:01:13

请问楼主第二题在地里有详解吗，找了一圈没找到

z920631580 · 2018-10-16 00:09:20

21212131 发表于 2018-10-14 17:01
请问楼主第二题在地里有详解吗，找了一圈没找到

我没仔细搜，大概就是sort + binary search

狗家 Intern 十月九 新OA