J****R
发帖数: 373 | 1 题目问的不难，但是我答题的时候脑子有点短路，等挂了电话以后开始恍然大悟，呵呵
。不管怎么样，在此表示感谢！
题目如下，供大家嘲笑一下：）
有如下机票：
LA-NY
NY-NV
NV-ATL
ATL-DC
SFO-LA
要求找出从头到尾的机票顺序：SFO-LA-NY-NV-ATL-DC
挺简单的一个题目，我吭哧了20多分钟，最后想出来了，还不是最简单的方法。 |
t*********h
发帖数: 941 | 2 头尾各出现一次吧 找到后穿起来就醒了 O(N)
【在 J****R 的大作中提到】
: 题目问的不难，但是我答题的时候脑子有点短路，等挂了电话以后开始恍然大悟，呵呵
: 。不管怎么样，在此表示感谢！
: 题目如下，供大家嘲笑一下：）
: 有如下机票：
: LA-NY
: NY-NV
: NV-ATL
: ATL-DC
: SFO-LA
: 要求找出从头到尾的机票顺序：SFO-LA-NY-NV-ATL-DC
|
J****R
发帖数: 373 | 3 对的，但我当时没想明白，净琢磨怎么hash了。
【在 t*********h 的大作中提到】
: 头尾各出现一次吧 找到后穿起来就醒了 O(N)
|
d**********x
发帖数: 4083 | 4 You need to merge disjoint cycles. Otherwise you may miss this test data:
LA-NY
NY-SFO
NY-DC
DC-ATL
ATL-NY
呵呵
【在 t*********h 的大作中提到】
: 头尾各出现一次吧 找到后穿起来就醒了 O(N)
|
J****R
发帖数: 373 | 5 是的，后来为了简单化，cycle的情况被排除了。
我的思路是建2个hashtable:
hashtable1
hashtable2
从第一张机票开始找，用hashtable1找到后面的iterate,然后反过来，用hashtable2找
到之前的iterate.
【在 d**********x 的大作中提到】
: You need to merge disjoint cycles. Otherwise you may miss this test data:
: LA-NY
: NY-SFO
: NY-DC
: DC-ATL
: ATL-NY
:
: 呵呵
|
h****n
发帖数: 1093 | 6 典型的topological sorting吧？
【在 J****R 的大作中提到】
: 题目问的不难，但是我答题的时候脑子有点短路，等挂了电话以后开始恍然大悟，呵呵
: 。不管怎么样，在此表示感谢！
: 题目如下，供大家嘲笑一下：）
: 有如下机票：
: LA-NY
: NY-NV
: NV-ATL
: ATL-DC
: SFO-LA
: 要求找出从头到尾的机票顺序：SFO-LA-NY-NV-ATL-DC
|
t*********h
发帖数: 941 | 7 如果复杂情况的话 比如有cycle和multiple path 要先建立graph 在bfs找shortest
path 就变的和上面的word ladder本质一样了
【在 d**********x 的大作中提到】
: You need to merge disjoint cycles. Otherwise you may miss this test data:
: LA-NY
: NY-SFO
: NY-DC
: DC-ATL
: ATL-NY
:
: 呵呵
|
d**********x
发帖数: 4083 | 8 bfs最短路径。。只是找一条路吧？
我的意思是说，实际上要找的可能是个从0入度节点开始到0出度节点的euler
traversal
当然后来lz补充说复杂情形去掉了。。所以就忽略吧
【在 t*********h 的大作中提到】
: 如果复杂情况的话 比如有cycle和multiple path 要先建立graph 在bfs找shortest
: path 就变的和上面的word ladder本质一样了
|
f*****e
发帖数: 2992 | 9 Eulerian traversal有现成的非常有趣的算法，那本combinatorial generation书里有
，虽然写的乱七八糟，不过还是有部分价值。不过这题好像是经过每个node一次，不是
经过每条edge一次。
【在 d**********x 的大作中提到】
: bfs最短路径。。只是找一条路吧？
: 我的意思是说，实际上要找的可能是个从0入度节点开始到0出度节点的euler
: traversal
: 当然后来lz补充说复杂情形去掉了。。所以就忽略吧
|
d**********x
发帖数: 4083 | 10 这道题是每个edge一次啊。。。
你想想机票是干啥的 = =|||
【在 f*****e 的大作中提到】
: Eulerian traversal有现成的非常有趣的算法，那本combinatorial generation书里有
: ，虽然写的乱七八糟，不过还是有部分价值。不过这题好像是经过每个node一次，不是
: 经过每条edge一次。
|
