Amazon onsite 跪经

LZ  请教第三问用树解是什么意思啊 有什么思路吗

求问楼主， jump gameII 要求返回jump path，用树怎么解呀？

xiaoniqiuqiu 发表于 2016-2-9 03:31
求问楼主， jump gameII 要求返回jump path，用树怎么解呀？

@elvisxyu  比如 [3,1,2,0,3]，构造的树就是类似这样的:
       (0)
     /  |  \
(1)  (2)   (3)
|       / \
(2)  (3)  (4)
|  \
(3) (4)

Doradus 发表于 2016-2-9 07:01
@elvisxyu  比如 [3,1,2,0,3]，构造的树就是类似这样的:
       (0)
     /  |  \

谢谢楼主！需要真的构造出树来嘛？还是写成循环的形式也可以呀？

Doradus 发表于 2016-2-9 07:01
@elvisxyu  比如 [3,1,2,0,3]，构造的树就是类似这样的:
       (0)
     /  |  \

我之前想的是用backtrack来找出能到末端的所有path，如果用树的话，看起来更高效耶。
构造和查询的时间复杂度也就O(n)

第一面和第二面的题怎么解？

楼主， 第三轮的时候， 这个jump game 是不是要求返回所有的路径？ 如果是返回最小的，用tree解怎么行？

269644943 发表于 2016-2-15 15:21
楼主， 第三轮的时候， 这个jump game 是不是要求返回所有的路径？ 如果是返回最小的，用tree解怎么行？

求出树了自然好得到最小值了，就相当于让你求所有root到leave的路径，取最短那个。

用树解应该就是用DFS或者BFS解吧

xiaoniqiuqiu 发表于 2016-2-9 03:31
求问楼主， jump gameII 要求返回jump path，用树怎么解呀？

如果只是求最优path，用greedy也是可以记录path的