logo
Redian新闻
>未名空间
>astrology - 星座物语
>
请辞Astrology星座版版主 (转载)
avatar
请辞Astrology星座版版主 (转载)# astrology - 星座物语
j*n
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,....
我想重新把链表建立起来，应该用什么样的算法?
谢谢.
avatar
j*8
2 楼
爸妈过来帮忙照顾儿子，现想买一个比较firm的床垫放楼上给妈妈用（这样可以玩上轮
流和我照看儿子）。 考虑买一个Full size的，还要妈妈也喜欢，儿子长大了也可以用
的。不知道大家有什麽可以推荐的。谢谢先了！
avatar
c*o
3 楼
跨区1000，湖南户口去的广州签证，从没出过国
就问了两个问题：是第一次去美国吗？去过别的国家吗？
avatar
h*e
4 楼
【 以下文字转载自 board 讨论区 】
发信人: hiddenlake (虚竹), 信区: board
标 题: 请辞Astrology星座版版主
发信站: BBS 未名空间站 (Mon Jul 11 10:46:26 2011, 美东)
再次感谢星星们的支持和宽容
感谢版副们的辛勤工作
祝福星版和星版的朋友们 ：）
avatar
m*f
5 楼
假设cell为x1,x2,x3,x4...
, ...
, ...
...
把这些pair基于第二个element排序, 每个整数出现了两次, 且在结果中相邻, 遍历结
果就可知哪些cell头尾相连
O(nlogn) time, O(n) space
avatar
w*r
6 楼
queen得好吧。。。 我当初买了一个full,现在觉得如果父母两个人都来的话太小了。
avatar
c*n
7 楼
cong
avatar
h*e
8 楼
已请辞，感兴趣申请版主的星星们赶快行动吧 ：）
avatar
j*n
9 楼

这个想法不错，挺简单的。效率有多高阿?
avatar
B*1
10 楼
Online order a Queen size firm mattress around $450.
I doubt the new mattress could last until your son turns 10 since you
probably would sell it at the 7th year.
avatar
p*d
11 楼
恭喜
avatar
h*e
12 楼
小手绢挥泪告别兔兔美女 ～～
avatar
m*f
13 楼
如果是naive matrix, O(n^2) space O(V^3) time (F-W algorithm? not sure)
如果采用了sparse matrix储存, 好像可以到linear time.

【在 j*****n 的大作中提到】
:
: 这个想法不错，挺简单的。效率有多高阿?
avatar
v*e
14 楼
我家儿子一个人用king的.晚上睡觉随他滚.
avatar
j*s
15 楼
cong!
avatar
z*x
16 楼
感谢多才心善的斑竹！ 非常喜欢你的blog...
avatar
j*n
17 楼

没怎么看明白, x1_start，x1_end， 这些是什么阿? 是基于哪个element排序阿?
望指教。 谢谢

【在 m*****f 的大作中提到】
: 假设cell为x1,x2,x3,x4...
: , ...
: , ...
: ...
: 把这些pair基于第二个element排序, 每个整数出现了两次, 且在结果中相邻, 遍历结
: 果就可知哪些cell头尾相连
: O(nlogn) time, O(n) space
avatar
j*8
18 楼
爸妈现在楼下用的是queen的.爸爸睡眠不好,不能熬夜. 只有把妈妈请到楼上和我轮流
照看儿子.儿子现在才六个月大,还在睡他的Crib.想要买的新床垫是想等crib及toddler
bed 以后用的. 所以大家觉得与其买个Full以后再换 Queen 还不如一次就买个Queen?
请问在哪里买适合孩子睡的床垫呢? 请推荐推荐!不甚感激!
avatar
m*1
19 楼
恭喜
avatar
t*c
20 楼
梦姑招lz，我们都祝福幸福哦。不过别忘了多来灵鹫星星宫看看我们哦。
avatar
h*k
21 楼
V^3怎么出来的？

【在 m*****f 的大作中提到】
: 如果是naive matrix, O(n^2) space O(V^3) time (F-W algorithm? not sure)
: 如果采用了sparse matrix储存, 好像可以到linear time.
avatar
A*A
22 楼
没有必要买queen吧如果给他一个人睡。我们家2个都是full size，而且是直接吃crib
到full size。 toddler bed从来没买过。 呵呵。。。 我们都是16-18个月之间换的，
睡得很好。
avatar
f*u
23 楼
也祝版大事事顺利。
avatar
j*n
24 楼

恩，发现cs的这些算法理论还真有用。当初还是该学cs。

【在 m*****f 的大作中提到】
: 如果是naive matrix, O(n^2) space O(V^3) time (F-W algorithm? not sure)
: 如果采用了sparse matrix储存, 好像可以到linear time.
avatar
j*8
25 楼
请问你给孩子买的哪个牌子？
avatar
L*n
26 楼
虚竹，一路走好，呜呜呜
avatar
m*f
27 楼
Floyd Warshall算法, brute force解决贝

【在 h**k 的大作中提到】
: V^3怎么出来的？
avatar
p*g
28 楼
我家买的是Sealy这个牌子里最firm的那种床垫，真的非常firm,已经买两个了，同一种
类的，一个king我们睡，一个full孩子睡，具体那个型号的名字不记得了，你要感兴趣
晚上回家我给你查查。

【在 j*****8 的大作中提到】
: 爸妈过来帮忙照顾儿子，现想买一个比较firm的床垫放楼上给妈妈用（这样可以玩上轮
: 流和我照看儿子）。 考虑买一个Full size的，还要妈妈也喜欢，儿子长大了也可以用
: 的。不知道大家有什麽可以推荐的。谢谢先了！
avatar
m*h
29 楼
小手绢挥泪告别兔兔美女 ～～
avatar
m*f
30 楼
x1_start就是指x1 cell 的start 整数是a, 用来做个标记而已
基于整数排序

【在 j*****n 的大作中提到】
:
: 恩，发现cs的这些算法理论还真有用。当初还是该学cs。
avatar
A*A
31 楼
searly， serta都可以，买个firm的就好了。
avatar
h*e
32 楼
555，谢谢大家，有空的时候肯定会回来的
估计不当版主了灌水更随意了呢还，呵呵
avatar
h*k
33 楼
不用这么复杂吧，每个cell不是已经记录了下个点的信息么？直接找到下个点不就行了
，使用hash table或者建个数组。

【在 m*****f 的大作中提到】
: Floyd Warshall算法, brute force解决贝
avatar
j*8
34 楼
ANA 谢谢你！ Pipiniang麻烦你帮我查一下你们家用的，谢谢啦！
avatar
z*a
35 楼
祝师兄美女一切顺利：）
avatar
V*0
36 楼
觉得是

【在 h**k 的大作中提到】
: 不用这么复杂吧，每个cell不是已经记录了下个点的信息么？直接找到下个点不就行了
: ，使用hash table或者建个数组。
avatar
b*d
37 楼
Why can't you take care of your son by yourself during night? It's very bad
for old people to not have a good sleep.

toddler
Queen?

【在 j*****8 的大作中提到】
: 爸妈现在楼下用的是queen的.爸爸睡眠不好,不能熬夜. 只有把妈妈请到楼上和我轮流
: 照看儿子.儿子现在才六个月大,还在睡他的Crib.想要买的新床垫是想等crib及toddler
: bed 以后用的. 所以大家觉得与其买个Full以后再换 Queen 还不如一次就买个Queen?
: 请问在哪里买适合孩子睡的床垫呢? 请推荐推荐!不甚感激!
avatar
k*u
38 楼
这个咋听着那么复杂

【在 z***a 的大作中提到】
: 祝师兄美女一切顺利：）
avatar
g*y
39 楼
我也觉得不用那么复杂hash就可以了吧?

【在 h**k 的大作中提到】
: 不用这么复杂吧，每个cell不是已经记录了下个点的信息么？直接找到下个点不就行了
: ，使用hash table或者建个数组。
avatar
p*g
40 楼
是Sealy的OAK ESTATES LTD FIRM

【在 j*****8 的大作中提到】
: ANA 谢谢你！ Pipiniang麻烦你帮我查一下你们家用的，谢谢啦！
avatar
l*e
41 楼
ah! 舍不得啊...
avatar
j*n
42 楼
我都忘了hash是怎么回事了，谢谢大家。回去看看书
avatar
j*8
43 楼
谢谢 pipiniang!
avatar
A*8
44 楼
co 祝你一切顺利

【在 z***a 的大作中提到】
: 祝师兄美女一切顺利：）
avatar
j*n
45 楼
再问个问题，
如果每个cell里面是没有方向的，只考虑连接情况
就是说cell可以是这样的， a-d, c-e, c-b,...,d-b,....
我想重新把链表建立起来，对应的链表还是 adbce....
还能用hash么？
谢谢
avatar
s*m
46 楼
送给亲爱的虚竹~
where your treasure is, there will your heart be also. : )

【在 h********e 的大作中提到】
: 555，谢谢大家，有空的时候肯定会回来的
: 估计不当版主了灌水更随意了呢还，呵呵
avatar
h*k
47 楼
能，只要你cell里记录的顺序是按照实际链表指向的顺序记录的。

【在 j*****n 的大作中提到】
: 再问个问题，
: 如果每个cell里面是没有方向的，只考虑连接情况
: 就是说cell可以是这样的， a-d, c-e, c-b,...,d-b,....
: 我想重新把链表建立起来，对应的链表还是 adbce....
: 还能用hash么？
: 谢谢
avatar
E*T
48 楼
真辞职啊！～～～55555
avatar
j*n
49 楼

哦 就是说如果我只记录 c和a 是连起来的， 但不记录是从c到a还是从a到c， 就不能
用hash了?

【在 h**k 的大作中提到】
: 能，只要你cell里记录的顺序是按照实际链表指向的顺序记录的。
avatar
s*i
50 楼
你要幸福快乐啊:)
avatar
h*k
51 楼
可以，稍微复杂一些。每个cell要分别按照其中的node存一次。比如cell: c-a，既要存
到node c这一项，也要存到node a这一项。而且重构的链表可能和原来的方向相反。

【在 j*****n 的大作中提到】
:
: 哦 就是说如果我只记录 c和a 是连起来的， 但不记录是从c到a还是从a到c， 就不能
: 用hash了?
avatar
G*r
52 楼
支持，祝福~
兔兔是个好人：）
avatar
j*n
53 楼
我想了这个简单办法,
假设 节点是从 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 找出来, .....
这个办法算有效的吗?
avatar
h*e
54 楼
谢谢，谢谢！
金玉良言啊 ：）
And I love peanuts!

【在 s******m 的大作中提到】
: 送给亲爱的虚竹~
: where your treasure is, there will your heart be also. : )
avatar
Z*Z
55 楼
一个是给了一组《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,....
: 我想重新把链表建立起来，应该用什么样的算法?
avatar
h*e
56 楼
谢谢！
动画好可爱啊 ：）

【在 s*******i 的大作中提到】
: 你要幸福快乐啊:)
avatar
Z*Z
57 楼
自顶一下！

【在 Z*****Z 的大作中提到】
: 一个是给了一组《id，parent id》对，如何重构出原来的树。
: 一个是给了一组《id，parent id》对，并且已知构建出来的一定是个链表，怎么做。
avatar
h*e
58 楼
谢谢凯普，一直特别支持，感谢 ：）

【在 G****r 的大作中提到】
: 支持，祝福~
: 兔兔是个好人：）
avatar
l*a
59 楼
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 的大作中提到】
: 自顶一下！
avatar
p*t
60 楼
这么快就走阿。 时间过得可真快。。。

【在 h********e 的大作中提到】
: 谢谢凯普，一直特别支持，感谢 ：）
avatar
Z*Z
61 楼
嗯，这个原题好像表述也不是很清楚。比如考虑最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
avatar
h*e
62 楼
是啊，流光容易把人抛啊。。
小帅粉也一切顺利啊 ：）

【在 p**********t 的大作中提到】
: 这么快就走阿。 时间过得可真快。。。
avatar
p*7
63 楼
这个题用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里面的元素
相关阅读
小声问一句：星星们网恋过嘛？写给所有另一半是天蝎的朋友蝎子来灌点水做男人最容易啦ZZ:处女座研究报告不可能禁欲的星座男生还是星版好什么星座的男生会最疼你呢（zz)终于找到座版了。。。。十二星座足球明星分析（转载）双鱼座之十二生肖个性大解析（转载）十二星座情人节送礼物高招(ZZ)2009年鸿运当头的星座（转载）二零零八年过去了，我很想念它。西方星象学综述（转载）蝎蝎进来：一个关于天蝎的问题珍爱生命，远离瓶男小调查：12星座小时候的理想实现了吗亲历12段情史，我眼中的这12宫男人们啊（水瓶女）（ZZ)双子座的忏悔：出来混，总是要还的
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。