一只兔子最多可以跳50厘米远。它想渡到河的另一边，但它不会游泳。所以唯一的希望就是跳上河上的岩石，这些岩石位于一条直线上。假设兔子从 0 厘米标记处开始测量岩石的位置。对岸可以被视为一块大石头。它是岩石元组中的最后一块岩石。
例如，岩石位于位置32、46、70、85、96、123，对面河岸位于位置 145。 对于上面的例子，它需要在岩石 0(起点)、岩石 46 和岩石 96 处进行 3 次跳跃才能到达另一侧(岩石 146)。
兔子每次跳都会跳得越远越好。到达河的另一边需要的最小跳跃次数是多少？
您可能会假设最多有 20 块岩石(包括对岸)。
编写一个函数 rabbit，该函数在表示岩石位置的元组中读取。您的函数应返回所需的最小跳跃次数，如果兔子无法到达河的另一边，则返回 -1。您可以假设元组中岩石的位置有效(大于 0)，并且它们按升序排序。
def rabbit(rocks):
jumps = 0
prev = 0
cursor = 0
i = 0
while i < len(rocks):
rock = rocks[i]
if rock - prev < 50:
cursor = rock
i += 1
continue
elif rock - prev >= 50 and prev != cursor:
jumps += 1
prev = cursor
continue
else:
return -1
if i == len(rocks):
rock = rocks[i-1]
if rock - prev <= 50:
jumps += 1
if jumps == 0:
return -1
return jumps
这里有一些案例：
兔子((32， 46， 70， 85， 96， 123， 145)) 应该生成 3。但我得到了 4 个。
兔子((30， 70， 75， 120， 160， 170， 180， 190， 200， 246， 258)) 和这种情况。最后一跳有问题。虽然我得到了 7 的答案，但代码的最后一部分似乎与第一种情况相矛盾。
我更改了部分代码，如下所示。
if rock - prev <= 50:
cursor = rock
i += 1
continue
elif rock - prev > 50 and prev != cursor:
jumps += 1
prev = cursor
continue
由于兔子最多可以跳50，那就意味着它可以跳50，所以需要rock - prev <= 50，而且它不能跳超过50，这是由rock - prev > 50 and prev != cursor覆盖
的在此之后，我得到如下输出：
print(rabbit((32, 46, 70, 85, 96, 123, 145)))
#3
print(rabbit((30, 70, 75, 120, 160, 170, 180, 190, 200, 246, 258)))
#7
使用递归的替代解决方案：
def rabbit(rocks, jumps=0):
max_jump = max(element for element in rocks if element <= 50)
last = rocks[-1]
if max_jump >= last:
return jumps + 1
else:
return rabbit([rock - max_jump for rock in rocks if rock > 50], jumps + 1)
print(rabbit([32, 46, 70, 85, 96, 123, 145]))
print(rabbit([30, 70, 75, 120, 160, 170, 180, 190, 200, 246, 258]))
输出：
3
7
这是我的解决方案：
MAX_JUMP_DIS = 50
def rabbit(rocks):
ans_rock = []
def jump(rocks, cur_pos=0):
list_possible = [rock for rock in rocks if rock <= MAX_JUMP_DIS + cur_pos]
if len(list_possible) == 0:
return -1
jump_pos = max(list_possible)
ans_rock.append(jump_pos)
[rocks.remove(rock) for rock in list_possible]
if len(rocks) != 0:
return jump(rocks, cur_pos=jump_pos)
if jump(rocks) == -1:
print(-1)
else:
print(f"rock list: {ans_rock} count:{len(ans_rock)}")
rabbit([32, 46, 70, 85, 96, 123, 7000])
rabbit([32, 46, 70, 85, 96, 123, 145])
rabbit([30, 70, 75, 120, 160, 170, 180, 190, 200, 246, 258])
输出：
-1
rock list: [46, 96, 145] count:3
rock list: [30, 75, 120, 170, 200, 246, 258] count:7