Snapchat电面

请问什么是“从高到低”？？

小A要当码农 发表于 2016-11-3 23:42
嗯。 前半部分N＊M是算上打印路径的时间了么？ 楼主优化了以后应该就是O（NM）了吧

N*M应该是每个点都要算一遍产生的，因为每个点都要重新计算一遍

luofeidream 发表于 2016-11-4 01:55
N*M应该是每个点都要算一遍产生的，因为每个点都要重新计算一遍

嗯。 理解了， 多谢！

电面之前有coding challenge吗？

shuiguo 发表于 2016-11-3 23:48
请问什么是“从高到低”？？

数字大小

longest path in a directed graph

BFS 也比较容易 从图上最后的节点开始往前推，一直遍历完所有的节点

111180611 发表于 2016-11-4 02:54
电面之前有coding challenge吗？

我没有。。

楼主 想问下是求递减的最长路径的长度还是具体的路径？如果只是求长度， 是不是就另外建一个int[][] cache存， 如果是具体路径是不是得每个节点cache一个list....建一个List<Integer>[][]的东西....

ayagan 发表于 2016-11-4 06:13
楼主 想问下是求递减的最长路径的长度还是具体的路径？如果只是求长度， 是不是就另外建一个int[][] cache ...

问的是长度，你的方案可行

jwl2006 发表于 2016-11-4 06:33
问的是长度，你的方案可行

谢谢楼主！祝拿到offer!