pocket gems电面跪经

cszhazha · 2017-11-16 08:08:18

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

x

说一个刚刚结束的宝石家电面，题就是maxsum tree path,但是

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

里网上好像都没怎么给这道题的解法。。

cszhazha · 2017-11-17 08:54:11

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

百晓生 · 2017-11-17 14:32:38

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

百晓生 · 2017-11-16 09:45:19

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

cszhazha · 2017-11-16 10:28:28

百晓生发表于 2017-11-16 09:45
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点 ...

但是要输出路径的，返回值是一个List<Node>

eyannnnn · 2017-11-16 12:38:01

想请问一下楼主，如果把list换成linkedList能保证时间复杂度O(n)么

cszhazha · 2017-11-16 12:39:28

eyannnnn 发表于 2017-11-16 12:38
想请问一下楼主，如果把list换成linkedList能保证时间复杂度O(n)么

感觉是可以的，但是这个解法不是面试官最想要的

eyannnnn · 2017-11-16 12:50:13

cszhazha 发表于 2017-11-16 12:39
感觉是可以的，但是这个解法不是面试官最想要的

谢谢楼主回复！不知道面试官希望要什么样的解法。。。

百晓生 · 2017-11-16 12:56:33

eyannnnn 发表于 2017-11-16 12:50
谢谢楼主回复！不知道面试官希望要什么样的解法。。。

那这个O（n）有点难啊最差的情况次还要把path再更新。。。LC上面因为只要返回int 可以达到O（n）。。。这个感觉只能用linkedlist了。。。谢谢楼主分享

tianbingleng · 2017-11-17 06:12:30

请问楼主面的是一面还是二面？谢谢

百晓生 · 2017-11-17 06:18:22

每次把最大sum子节点的list直接赋值被当前节点的list（不要重新添加）然后这个list再加上当前的value。右子节点就改成和左子节点的path一样就好了，然后碰到最大值的时候 reverse一下右子节点然后一起存到maxlist里面应该就可以达到O（n）了