j*****n
发帖数: 1545 | 1 【 以下文字转载自 CS 讨论区 】
发信人: jetchen (飞机), 信区: CS
标 题: 问一个链表方面的算法问题
发信站: BBS 未名空间站 (Sun Jan 24 00:08:52 2010, 美东)
小弟EE的，不是cs科班出生，不知道这个问题描述的准不准确：
有一个循环链表 a->d->b->c->e->....->a
每一个节点都是一个整数，且不重复(除了首尾节点外)。
现在这个链表被拆断开了，每2个相邻节点被存在一个cell里面, 但这些cell不是有序
的。 就是说链表被拆成了 a->d, c->e,...,d->b,...,b->c,....
我想重新把链表建立起来，应该用什么样的算法?
谢谢. |
m*****f
发帖数: 1243 | 2 假设cell为x1,x2,x3,x4...
, ...
, ...
...
把这些pair基于第二个element排序, 每个整数出现了两次, 且在结果中相邻, 遍历结
果就可知哪些cell头尾相连
O(nlogn) time, O(n) space |
j*****n
发帖数: 1545 | |
m*****f
发帖数: 1243 | 4 如果是naive matrix, O(n^2) space O(V^3) time (F-W algorithm? not sure)
如果采用了sparse matrix储存, 好像可以到linear time.
【在 j*****n 的大作中提到】
:
: 这个想法不错，挺简单的。效率有多高阿?
|
j*****n
发帖数: 1545 | 5
没怎么看明白, x1_start，x1_end， 这些是什么阿? 是基于哪个element排序阿?
望指教。 谢谢
【在 m*****f 的大作中提到】
: 假设cell为x1,x2,x3,x4...
: , ...
: , ...
: ...
: 把这些pair基于第二个element排序, 每个整数出现了两次, 且在结果中相邻, 遍历结
: 果就可知哪些cell头尾相连
: O(nlogn) time, O(n) space
|
h**k
发帖数: 3368 | 6 V^3怎么出来的？
【在 m*****f 的大作中提到】
: 如果是naive matrix, O(n^2) space O(V^3) time (F-W algorithm? not sure)
: 如果采用了sparse matrix储存, 好像可以到linear time.
|
j*****n
发帖数: 1545 | 7
恩，发现cs的这些算法理论还真有用。当初还是该学cs。
【在 m*****f 的大作中提到】
: 如果是naive matrix, O(n^2) space O(V^3) time (F-W algorithm? not sure)
: 如果采用了sparse matrix储存, 好像可以到linear time.
|
m*****f
发帖数: 1243 | 8 Floyd Warshall算法, brute force解决贝
【在 h**k 的大作中提到】
: V^3怎么出来的？
|
m*****f
发帖数: 1243 | 9 x1_start就是指x1 cell 的start 整数是a, 用来做个标记而已
基于整数排序
【在 j*****n 的大作中提到】
:
: 恩，发现cs的这些算法理论还真有用。当初还是该学cs。
|
h**k
发帖数: 3368 | 10 不用这么复杂吧，每个cell不是已经记录了下个点的信息么？直接找到下个点不就行了
，使用hash table或者建个数组。
【在 m*****f 的大作中提到】
: Floyd Warshall算法, brute force解决贝
|
|
|
V**0
发帖数: 889 | 11 觉得是
【在 h**k 的大作中提到】
: 不用这么复杂吧，每个cell不是已经记录了下个点的信息么？直接找到下个点不就行了
: ，使用hash table或者建个数组。
|
g*******y
发帖数: 1930 | 12 我也觉得不用那么复杂hash就可以了吧?
【在 h**k 的大作中提到】
: 不用这么复杂吧，每个cell不是已经记录了下个点的信息么？直接找到下个点不就行了
: ，使用hash table或者建个数组。
|
j*****n
发帖数: 1545 | 13 我都忘了hash是怎么回事了，谢谢大家。回去看看书 |
j*****n
发帖数: 1545 | 14 再问个问题，
如果每个cell里面是没有方向的，只考虑连接情况
就是说cell可以是这样的， a-d, c-e, c-b,...,d-b,....
我想重新把链表建立起来，对应的链表还是 adbce....
还能用hash么？
谢谢 |
h**k
发帖数: 3368 | 15 能，只要你cell里记录的顺序是按照实际链表指向的顺序记录的。
【在 j*****n 的大作中提到】
: 再问个问题，
: 如果每个cell里面是没有方向的，只考虑连接情况
: 就是说cell可以是这样的， a-d, c-e, c-b,...,d-b,....
: 我想重新把链表建立起来，对应的链表还是 adbce....
: 还能用hash么？
: 谢谢
|
j*****n
发帖数: 1545 | 16
哦 就是说如果我只记录 c和a 是连起来的， 但不记录是从c到a还是从a到c， 就不能
用hash了?
【在 h**k 的大作中提到】
: 能，只要你cell里记录的顺序是按照实际链表指向的顺序记录的。
|
h**k
发帖数: 3368 | 17 可以，稍微复杂一些。每个cell要分别按照其中的node存一次。比如cell: c-a，既要存
到node c这一项，也要存到node a这一项。而且重构的链表可能和原来的方向相反。
【在 j*****n 的大作中提到】
:
: 哦 就是说如果我只记录 c和a 是连起来的， 但不记录是从c到a还是从a到c， 就不能
: 用hash了?
|
j*****n
发帖数: 1545 | 18 我想了这个简单办法,
假设 节点是从 0-10,
建一个n*2的矩阵, 先遍历所有cell，假设i-j在一个cell里, 则把矩阵的第i行的第0或
者第1列(看哪列是空的)置成j. 这样就把这个矩阵都能填满.
然后把这个矩阵遍历一遍, 就能把这个链表建立起来了。
比如 链表是 0-5-2-3-9,... 我先把 0 和 5 push到link里面去, 然后去看matrix第5
行, 把非0的那个entry 2找出来，push 到 link里面去； 然后去看matrix第2行把非5
的那个entry 3 找出来, .....
这个办法算有效的吗? |
Z*****Z
发帖数: 723 | 19 一个是给了一组《id，parent id》对，如何重构出原来的树。
一个是给了一组《id，parent id》对，并且已知构建出来的一定是个链表，怎么做。
【在 j*****n 的大作中提到】
: 【 以下文字转载自 CS 讨论区 】
: 发信人: jetchen (飞机), 信区: CS
: 标 题: 问一个链表方面的算法问题
: 发信站: BBS 未名空间站 (Sun Jan 24 00:08:52 2010, 美东)
: 小弟EE的，不是cs科班出生，不知道这个问题描述的准不准确：
: 有一个循环链表 a->d->b->c->e->....->a
: 每一个节点都是一个整数，且不重复(除了首尾节点外)。
: 现在这个链表被拆断开了，每2个相邻节点被存在一个cell里面, 但这些cell不是有序
: 的。 就是说链表被拆成了 a->d, c->e,...,d->b,...,b->c,....
: 我想重新把链表建立起来，应该用什么样的算法?
|
Z*****Z
发帖数: 723 | 20 自顶一下！
【在 Z*****Z 的大作中提到】
: 一个是给了一组《id，parent id》对，如何重构出原来的树。
: 一个是给了一组《id，parent id》对，并且已知构建出来的一定是个链表，怎么做。
|
|
|
l*****a
发帖数: 14598 | 21 for the first one,how do u judge whether it is left node or right node?
for the second one,i think it is just the issue of this post
【在 Z*****Z 的大作中提到】
: 自顶一下！
|
Z*****Z
发帖数: 723 | 22 嗯，这个原题好像表述也不是很清楚。比如考虑最general的情况，如果不是二叉树呢？
【在 l*****a 的大作中提到】
: for the first one,how do u judge whether it is left node or right node?
: for the second one,i think it is just the issue of this post
|
p********7
发帖数: 549 | 23 这个题用hash可以实现复杂度O(N).
比如 a-d c-e d-b b-c 分别存在数组input[N],hash记录出现字母的位置
a b c d e f
0 0
1 1
2 2
如果字母出现过了，就连接2个input里面的元素 |
