割草机的前，后轮驱动各适用什么地面或各有什么好处？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

割草机的前，后轮驱动各适用什么地面或各有什么好处？

割草机的前，后轮驱动各适用什么地面或各有什么好处？# Living

l*a2012-05-24 07:05

1 楼

Given a circular linked list, implement an algorithm which returns node at
the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node¡ˉs next
pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C

i*w2012-05-24 07:05

2 楼

板上出现的3个电话都打过2次，都说等7-10天。。。

s*e2012-05-24 07:05

3 楼

或者或单一地说前驱好，或后驱好？

d*e2012-05-24 07:05

4 楼

career cup 150上面关于链表的好像有这题

next

【在 l*****a 的大作中提到】

: Given a circular linked list, implement an algorithm which returns node at
: the beginning of the loop.
: DEFINITION
: Circular linked list: A (corrupt) linked list in which a node¡ˉs next
: pointer points to an earlier node, so as to make a loop in the linked list.
: EXAMPLE
: Input: A -> B -> C -> D -> E -> C [the same C as earlier]
: Output: C

t*92012-05-24 07:05

5 楼

打了16个的路过

w*t2012-05-24 07:05

6 楼

前驱的适合平地懒人。后驱的适合坡地勤快人。

或者或单一地说前驱好，或后驱好？
★ Sent from iPhone App: iReader Mitbbs Lite 7.56

【在 s********e 的大作中提到】

: 或者或单一地说前驱好，或后驱好？

l*a2012-05-24 07:05

7 楼

是上面的。
看不懂答案。：（

【在 d**e 的大作中提到】

: career cup 150上面关于链表的好像有这题
:
: next

k*i2012-05-24 07:05

8 楼

今天还能申么?

【在 i******w 的大作中提到】

: 板上出现的3个电话都打过2次，都说等7-10天。。。

c*o2012-05-24 07:05

9 楼

前驱的适合推，后驱的适合拉

C*n2012-05-24 07:05

10 楼

1. 快慢两个指针，一个每次走一步，一个每次走两步，如果有环，那么他们肯定会相
遇，且相遇点在环里
2. 从（1）中找到的相遇点出发，绕着环走一圈，得到环的长度n
3. 从链表头开始，一个指针先走n步，然后两个指针开始一起走，每次一步，他们相遇
的点就是环的入口点

u*g2012-05-24 07:05

11 楼

他也是叫我等7～10biz days，我网上一查已经批了...

【在 i******w 的大作中提到】

: 板上出现的3个电话都打过2次，都说等7-10天。。。

l*a2012-05-24 07:05

12 楼

这个浅显易懂，谢谢。

【在 C*******n 的大作中提到】

: 1. 快慢两个指针，一个每次走一步，一个每次走两步，如果有环，那么他们肯定会相
: 遇，且相遇点在环里
: 2. 从（1）中找到的相遇点出发，绕着环走一圈，得到环的长度n
: 3. 从链表头开始，一个指针先走n步，然后两个指针开始一起走，每次一步，他们相遇
: 的点就是环的入口点

G*A2012-05-24 07:05

13 楼

求查status的link

【在 u********g 的大作中提到】

: 他也是叫我等7～10biz days，我网上一查已经批了...

g*e2012-05-24 07:05

14 楼

相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
比你的方法简单。

【在 C*******n 的大作中提到】

j*82012-05-24 07:05

15 楼

https://www.accountonline.com/cards/acq/CardApplicationStatus.do
baozi plz

【在 G****A 的大作中提到】

: 求查status的link

r*l2012-05-24 07:05

16 楼

可能永不相遇呢？

【在 g**e 的大作中提到】

: 相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
: 比你的方法简单。

G*A2012-05-24 07:05

17 楼

没法用. 申请完邮箱没收到任何邮件，所以没有app id
发包子了

【在 j*****8 的大作中提到】

: https://www.accountonline.com/cards/acq/CardApplicationStatus.do
: baozi plz

c*j2012-05-24 07:05

18 楼

if n is small, they won't meet

【在 C*******n 的大作中提到】

j*82012-05-24 07:05

19 楼

给客服电话要app id

【在 G****A 的大作中提到】

: 没法用. 申请完邮箱没收到任何邮件，所以没有app id
: 发包子了

r*h2012-05-24 07:05

20 楼

嗯，这个比较简单，，

【在 g**e 的大作中提到】

: 相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
: 比你的方法简单。

b*g2012-05-24 07:05

21 楼

yes

【在 k***i 的大作中提到】

: 今天还能申么?

h*82012-05-24 07:05

22 楼

怎么确定相遇的是起点？为什么呢？

【在 g**e 的大作中提到】

: 相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
: 比你的方法简单。

J*A2012-05-24 07:05

23 楼

你这个网站毛都没有啊。。。。

【在 j*****8 的大作中提到】

: https://www.accountonline.com/cards/acq/CardApplicationStatus.do
: baozi plz

g*e2012-05-24 07:05

24 楼

想一下他们为什么一定相遇在环的起始点

【在 r******l 的大作中提到】

: 可能永不相遇呢？

S*r2012-05-24 07:05

25 楼

try this one for status check:
https://www.accountonline.com/cards/acq/CardApplicationStatus.do?screenID=
3187
baozi plz

r*l2012-05-24 07:05

26 楼

根本不能保证相遇，哪来的为什么？

【在 g**e 的大作中提到】

: 想一下他们为什么一定相遇在环的起始点

J*A2012-05-24 07:05

27 楼

查到这个
Your welcome kit and card(s) will arrive in the mail within 2 weeks of the
above date at the address you provided.
毫无快递的迹象。。。
这个如何是好

【在 S*******r 的大作中提到】

: try this one for status check:
: https://www.accountonline.com/cards/acq/CardApplicationStatus.do?screenID=
: 3187
: baozi plz

l*c2012-05-24 07:05

28 楼

为什么不能保证相遇呢？是否找了例子呢？
Assume # of the nodes outside the loop is n1, # inside is n2. After you got
the n2, count n2 from the beginning, then the # of left uncounted nodes is
n1. So, even though we do not know n1, we can start to count from the
beginning and from the last counting ending point. After n1 steps, the first
counting process reaches the beginning of the loop, and the second counting
arrives the beginning of the loop, too.

【在 r******l 的大作中提到】

: 根本不能保证相遇，哪来的为什么？

w*r2012-05-24 07:05

29 楼

打电话问最快了

r*l2012-05-24 07:05

30 楼

你说的方法跟那个gate说的完全是两码事啊。

got
first
counting

【在 l****c 的大作中提到】

: 为什么不能保证相遇呢？是否找了例子呢？
: Assume # of the nodes outside the loop is n1, # inside is n2. After you got
: the n2, count n2 from the beginning, then the # of left uncounted nodes is
: n1. So, even though we do not know n1, we can start to count from the
: beginning and from the last counting ending point. After n1 steps, the first
: counting process reaches the beginning of the loop, and the second counting
: arrives the beginning of the loop, too.

l*c2012-05-24 07:05

31 楼

哦，我没看他那个方法。。。。
还以为在说我这种方法。。。。

【在 r******l 的大作中提到】

: 你说的方法跟那个gate说的完全是两码事啊。
:
: got
: first
: counting

t*t2012-05-24 07:05

32 楼

你仔细算算就发现, 其实就是一回事---关键是, 第一步相遇的地方就是离开头N步的地
方.

【在 r******l 的大作中提到】

: 你说的方法跟那个gate说的完全是两码事啊。
:
: got
: first
: counting

t*t2012-05-24 07:05

33 楼

你还是看看的好, 他的方法比你的简单.

【在 l****c 的大作中提到】

: 哦，我没看他那个方法。。。。
: 还以为在说我这种方法。。。。

c*t2012-05-24 07:05

34 楼

你的方法好。但最后那个指针，应该是每次移动一步吧？

【在 g**e 的大作中提到】

: 相遇以后，再弄个指针从head出发，每次移动两个指针一步，相遇的就是起始点。
: 比你的方法简单。

g*e2012-05-24 07:05

35 楼

你果然没想

【在 r******l 的大作中提到】

: 根本不能保证相遇，哪来的为什么？

w*o2012-05-24 07:05

36 楼

首先，为什么一定会相遇。假设p1是慢指针（每次走一步），p2是快指针（每次走两步
），c是环的起始点，也就是我们要找的点，并且假设环的长度是n。只要有环，p1迟早
要进入环，我们考虑p1进入环以后的情况。在p1完成一圈以前，p2必然超过p1一次。因
为p1完成一圈需要n步，而p2在这段时间内则走了2n步。那么我们考虑p2超越p1时的情
况。假设在这一步p1从节点a移到了节点b。如果p2要不想在节点b与p1相遇而超越b的话
，必然只能在节点a开始往前跳，因为p2每次只移动两步。而它如果从a开始的话，实际
上它们在上一步就已经相遇了。所以，p1和p2必然相遇。
第二点，如何找到c。假设从链表起点到c的距离是k1，从c到相遇点b的距离是k2。相遇
时，p1走了k1 + k2步，p2走了k1 + k2 + cn（c是一个大于0的整数，如果k1很长，而n
很短的话，p2在相遇之前可能已经空转了好几圈）。由于p2速度是p1速度的两倍，我们
有：
2 * (k1 + k2) = k1 + k2 + cn => k1 + k2 = cn
我们要求k1，所以
K1 = cn – k2 = (n – k2) + (c – 1) n
很显然，n – k2是从相遇点b到c的距离。假设k3 = n – k2，就有：
K1 = k3 + c1 * n
意思就是如果一个指针从链表起点走（每次一步），另一个指针从相遇点b转圈（每次
一步），它们必然在环起点c相遇。
很多人忽略了c1*n，虽然对结果没有什么影响，但应该明白，其实环内的指针可能转了
很多圈才与另一个指针相遇的。但不管怎么样它们必然在c相遇。