Google 2019summer Intern OA

Eric_Lin · 2018-10-10 11:12:31

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

x

第一题好像没在地里见到
给一颗树，和一个距离n，返回树上每个节点的与自

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

返回一个数组代表每个房子距离最近的商店的位置

nyjahchill · 2018-10-11 22:00:19

和三楼想法一样有没有优化呢

来自一亩三分地官方APP

lic120 · 2018-10-11 13:19:02

楼主，请问下第一题怎么做？

lic120 · 2018-10-11 13:39:49

lic120 发表于 2018-10-11 13:19
楼主，请问下第一题怎么做？

想了想，应该是通过索引值找，但是worst case下应该是n方复杂度，不知道怎么优化？

OJASHAHAHA · 2018-10-11 14:27:05

第一题最明显的暴力解应该是一个for loop走array，for loop里面一个while loop来找parent时 distance -1直到distance=0 或者找到了-1. 所以时间是O(distance*N) 空间是O(1).

求大神优化？

yubowang1996 · 2018-10-11 21:46:29

请问如果没有距离为N的祖先 return -1吗？比如说 [0, 0, 1, 1, 1] 然后 N = 2
顺便请问根的情况是在数组里用什么表示

nyjahchill · 2018-10-11 22:00:18

和三楼想法一样有没有优化呢

来自一亩三分地官方APP

catherinebiong · 2018-10-21 12:39:05

OJASHAHAHA 发表于 2018-10-11 14:27
第一题最明显的暴力解应该是一个for loop走array，for loop里面一个while loop来找parent时 distance -1直 ...

请问找到了-1是什么意思呢？是指数组里的存储值是-1吗？

Evan_ZYR · 2018-10-27 00:08:19

看这描述我第一反应是用双指针？