FibFrog Codility 问题 - 性能优化

Question

我正在尝试解决 FibFrog Codility 问题，我想出了以下方法：

如果 len(A) 为 0，我们知道我们可以一次跳到另一边。
如果len(A) + 1是一个斐波那契数，我们也可以一步跳到。
否则，我们循环遍历 A，对于我们可以到达的位置，我们检查是否可以使用斐波那契数 (idx + 1 in fibonaccis) 直接从 -1 到达它们，或者我们是否可以通过先跳转到达它们到另一个位置（reachables），然后跳转到当前位置。在任何一种情况下，我们还检查是否可以从当前位置走到河流的尽头 - 如果可以，那么我们可以 return 因为我们找到了所需的最少步数。
最后，如果 unreachable 是 True 一旦这个循环完成，这意味着我们无法使用斐波那契数到达任何位置，所以我们 return -1.

我使用这种方法 getting 正确率为 83%，性能为 0%。

我理解解决方案是 O(n^2)，假设数组仅包含 1，嵌套循环 for v in reachables: 将运行 n 次 - 但是我不确定我还能如何计算这个，因为对于每个位置，我需要检查我们是否可以从数组的开头到达它，或者使用斐波那契数从任何先前的位置到达它。

    def solution(A):
        if len(A) == 0: return 1 
        fibonaccis = fibonacci(len(A) + 3)
        if len(A) + 1 in fibonaccis: return 1
        leaves = [0] * len(A)
        unreachable = True
        reachables = []
        for idx, val in enumerate(A): 
            if val == 1: 
                if idx + 1 in fibonaccis: 
                    unreachable = False
                    leaves[idx] = 1
                    if len(A) - idx in fibonaccis: 
                        return 2
                    reachables.append(idx)
                elif len(reachables) > 0: 
                    for v in reachables: 
                        if idx - v in fibonaccis: 
                            leaves[idx] = leaves[v] + 1
                            if len(A) - idx in fibonaccis: 
                                return leaves[v] + 2
                            reachables.append(idx)
                            break
        if unreachable: return -1 
        if len(A) - reachables[-1] in fibonaccis: 
            return leaves[reachables[-1]] + 1
    
    def fibonacci(N): 
        arr = [0] * N
        arr[1] = 1
        for i in range(2, N): 
            arr[i] = arr[i-1] + arr[i-2]
        return arr

Answer 1

提高算法性能的一些建议 -

如果len(A) = 100000，您正在计算 100003 个斐波那契数，而我们只需要小于 100k 的斐波那契数，即 <30 个。
您的解决方案是 O(n^4)，因为每个 X in reachables 或 Y in fibonaccis 操作都是 O(N)，其中 N 是 len(A)。（由于上述问题，fibonaccis 的长度为 N）
由于您在 fibonaccis 和 reachables 上进行了大量 item in list 操作，请考虑将其设为 set 或 dictionary 以加快速度（ O(1) 而不是 O(n)) 查找。
即使进行了上述更改，由于 A 和 reachables 之间的嵌套循环，算法仍将是 O(N^2)，因此您需要想出更好的方法。

用你现有的实现，你需要遍历所有的路径，最后你会得到最少的跳转次数。

而不是这种方法，如果你从 0 开始，然后记录你到目前为止的跳跃次数，并保持你可以达到的距离（以及达到的次数）每次跳跃然后你可以很容易地找到到达终点所需的最小跳跃。（如果你在 A.

中拥有所有 1，这也将节省你必须做的冗余工作

例如对于

A = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
fibonacci = set(1, 2, 3, 5)

第一次跳转，我们可以到达以下从1开始的索引-

reachable = [1, 2, 3, 5]
jumps = 1

第二次跳跃后

reachables = [2, 3, 4, 5, 6, 7, 8]
jumps = 2

第三跳后

reachables = [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
jumps = 3

所以你跳了 3 次后到达了终点(10)。

请在此处查看@nialloc 的回答 - 似乎在做类似的事情。

Answer 2

另请查看我的解决方案，该解决方案在 Codility 测试中得分为 100%，并且易于理解。

想法是在k跳之后跟踪青蛙所有可能的位置。如果可能位置== n, return k.

def fib_up_to(n):
    numbers = [1]
    i = 1
    while True:
        new_num = (numbers[-2] + numbers[-1]) if i > 1 else 2
        if new_num > n:
            break
        numbers.append(new_num)
        i += 1
    return numbers

def solution(A):
    n = len(A)
    if n == 0:
        return 1
    numbers = fib_up_to(n+1)

    possible_positions = set([-1])
    for k in range(1, n+1):
        positions_after_k = set()
        for pos in possible_positions:
            for jump in numbers:
                if pos + jump == n:
                    return k
                if pos + jump < n and A[pos + jump]:
                    positions_after_k.add(pos + jump)
        possible_positions = positions_after_k
    return -1

FibFrog Codility 问题 - 性能优化

FibFrog Codility Problem - Optimising for Performance

python

algorithm

time-complexity

fibonacci