t******e 发帖数: 1293 | 1 http://www.careercup.com/question?id=296729
Give two parking locations P1 and P2, P1 and P2 both have n slots. n-1 cars
with same IDs are parked in n-1 slots in both P1 and P2. Design an algorithm
to let n-1 cars in P1 and P2 park in the same slots
看了小尾羊的回复,还是没有很清楚。
首先题目的意思不是很明确,我的理解是每次只能动一辆车,只能把车移动空位上去。
以下面的例子为例
P1: 1 3 _ 4 2 5 先把 _ 移动最后 --> P1: 1 3 4 2 5 _
P2: 2 5 1 4 _ 3 --> P2: 2 5 1 4 3 _
分别对P1和P2进行qsort,假设_的取值等于(n+1)/2 + 0.5,也就是3.5,这样,我们分
别对P1和P2扫描并且交换,一趟之后,分别如下:
P1: 1 3 2 |
j*t 发帖数: 184 | 2 space只用来做buffer的吧。
“Design an algorithm to let n-1 cars in P1 and P2 park in the same slots”
要求P1和P2parking的一模一样。
这题不难吧? |
h**6 发帖数: 4160 | 3 设空位号为i
while(i
{
while(i
{
把i号车移动到空位
设置i号车原来的位置为空
}
if (有车没排好)
{
把第一个没排好的车移动到空位
设置i号车原来的位置为空
}
else break;
}
移动次数为错误车辆个数加环数,最多(n-1)/2个环,即需要移动(n-1)*3/2次 |
s*****o 发帖数: 1540 | 4 是不是我英语太差?我怎么一点不明白在说什么?
什么叫做同样ID的N-1辆车在P1,P2停车场?
cars
algorithm
【在 t******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.careercup.com/question?id=296729 : Give two parking locations P1 and P2, P1 and P2 both have n slots. n-1 cars : with same IDs are parked in n-1 slots in both P1 and P2. Design an algorithm : to let n-1 cars in P1 and P2 park in the same slots : 看了小尾羊的回复,还是没有很清楚。 : 首先题目的意思不是很明确,我的理解是每次只能动一辆车,只能把车移动空位上去。 : 以下面的例子为例 : P1: 1 3 _ 4 2 5 先把 _ 移动最后 --> P1: 1 3 4 2 5 _ : P2: 2 5 1 4 _ 3 --> P2: 2 5 1 4 3 _ : 分别对P1和P2进行qsort,假设_的取值等于(n+1)/2 + 0.5,也就是3.5,这样,我们分
|
S*********r 发帖数: 5693 | 5 哈哈,我还以为看不懂题目是因为是我太笨呢
【在 s*****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是不是我英语太差?我怎么一点不明白在说什么? : 什么叫做同样ID的N-1辆车在P1,P2停车场? : : cars : algorithm
|
g********d 发帖数: 203 | 6 既然all cars have same IDs,不需要sort吧?也不知道按什么sort
cars
algorithm
【在 t******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.careercup.com/question?id=296729 : Give two parking locations P1 and P2, P1 and P2 both have n slots. n-1 cars : with same IDs are parked in n-1 slots in both P1 and P2. Design an algorithm : to let n-1 cars in P1 and P2 park in the same slots : 看了小尾羊的回复,还是没有很清楚。 : 首先题目的意思不是很明确,我的理解是每次只能动一辆车,只能把车移动空位上去。 : 以下面的例子为例 : P1: 1 3 _ 4 2 5 先把 _ 移动最后 --> P1: 1 3 4 2 5 _ : P2: 2 5 1 4 _ 3 --> P2: 2 5 1 4 3 _ : 分别对P1和P2进行qsort,假设_的取值等于(n+1)/2 + 0.5,也就是3.5,这样,我们分
|