请教一道面试题 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 请教一道面试题

相关主题
● 问一个graph题	● 算法作业2
● Depth-First-Search	● 一道面试题
● 请叫大家一道题	● MS onsite 面经
● 求问一题G家的面经	● G家电面面经--佛云了~~
● 问一个面试题	● 二叉树最长路径用 level order travel 做？
● Amazon面试题请教	● L家这题咋搞，巨变态
● in what case O(n*2) is better than O(n).	● 一道linkedin的graph题
● 请教一下超大图的存储问题	● 一道C面试题

相关话题的讨论汇总
话题: a2话题: c3话题: b2话题: b3话题: b1

进入JobHunting版参与讨论

(共1页)

z**********f
发帖数: 74

有这样一些点:
a1 a2
b1 b2 b3
c1 c2 c3
现在手里面有map知道每个点的edges，比如这样:
a1->b1
a2->b1
a2->b2
a2->b3
b1->c1
b2->c2
b2->c3
b3->c3
然后Input知道第一层有哪些点是有用的，比如a2;也知道最后一层哪些点是有用的，比
如c2和c3;然后中间有些点是不能经过的，这里比如b2。
现在需要打印从第一层有用的点到最后一层中间可以经过的点（包括第一层和最后一层
有用的点本身），一个点只用打印一次。比如这个例子就应该打印:
a2 b3 c3
我尝试了一会用graph search+DFS找到所有路径，每条路径是一个array，然后把每条
路径的所有点存起来，最后把重复的点再删除掉，不过写了一会就没信心放弃了，
performance太糟糕了。然后想了想能不能用dp，比如bottom　up，每到一个node就把
所有通向该node的邻近nodes通通找出来，但是我不知道这个跟暴力搜索相比优化在哪
里。
请大牛提供一下思路或者解法，非常感谢。

k****r
发帖数: 807

DFS 为什么会有重复点呢

(共1页)

进入JobHunting版参与讨论

相关主题
● 一道C面试题	● 问一个面试题
● amazon一道面试题	● Amazon面试题请教
● 请教个面试题	● in what case O(n*2) is better than O(n).
● 报Google Offer并请教面试题	● 请教一下超大图的存储问题
● 问一个graph题	● 算法作业2
● Depth-First-Search	● 一道面试题
● 请叫大家一道题	● MS onsite 面经
● 求问一题G家的面经	● G家电面面经--佛云了~~

相关话题的讨论汇总
话题: a2话题: c3话题: b2话题: b3话题: b1

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天