2

兔子最多可以跳50厘米远。它想越过河的另一边，但它不会游泳。所以唯一的希望就是在河边的岩石上跳跃，这些岩石位于一条直线上。假设兔子从 0 厘米标记处开始，从起始位置开始测量岩石的位置。对岸可以被视为一块大石头。它是岩石元组中的最后一块岩石。

例如，岩石在位置 32、46、70、85、96、123，而对面的河岸在位置 145。对于上面的例子，它需要进行 3 次跳跃，在岩石 0（起点），岩石 46 ，然后岩石 96 到达另一侧（岩石 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

这里的一些案例：

rabbit((32, 46, 70, 85, 96, 123, 145)) 应该生成 3。但我得到了 4。

rabbit((30, 70, 75, 120, 160, 170, 180, 190, 200, 246, 258)) 并且对于这种情况。最后一跳有问题。虽然我得到了 7 的答案，但代码的最后一部分似乎与第一种情况相矛盾。

4

3 回答 3

2

我更改了部分代码，如下所示。

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
于 2019-04-23T05:15:07.670 回答
0

使用递归的替代解决方案：

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
于 2019-04-23T05:22:03.937 回答
0

这是我的解决方案：

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
于 2019-04-23T06:19:15.277 回答