FibFrog编码问题--性能优化

问题描述

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

1. 如果len(A)为0，我们知道可以一次跳跃到达对岸。
2. 如果len(A) + 1是斐波那契数，我们也可以一跳达到它。
3. 否则，我们循环A，对于我们可以到达的位置，我们检查是否可以使用斐波纳契数(idx + 1 in fibonaccis)直接从-1到达它们，或者是否可以通过先跳到另一个位置(reachables)然后跳到当前位置来到达它们。在这两种情况下，我们还会检查是否可以从当前位置走到河的尽头-如果可以，则可以返回，因为我们找到了所需的最小步数。
4. 最后，如果unreachable为True，则此循环完成后，这意味着我们无法使用斐波纳契数到达任何位置，因此返回-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

---

解决方案

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

• 如果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))查找速度。
• 即使进行了上述更改，算法仍然是O(N^2)，因为A和reachables之间存在嵌套循环，因此您需要想出更好的方法。

使用现有实现时，您需要遍历所有路径，然后最终将获得最少的跳转次数。

与此方法不同，如果您从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的答案-https://stackoverflow.com/a/64558623/8677071它似乎在做类似的事情。