我正在嘗試解決FibFrog Codility 問題，并提出了以下方法：
- 如果
len(A)是 0，我們知道我們可以在一次跳躍中到達另一邊。 - 如果
len(A) 1是斐波那契數，我們也可以一跳達到。 - 否則，我們回圈遍歷 A，對于我們可以到達的位置，我們檢查是否可以使用斐波那契數從 -1 直接到達它們，
(idx 1 in fibonaccis)或者我們是否可以通過先跳到另一個位置 (reachables) 然后跳到當前位置。在任何一種情況下，我們還會檢查是否可以從當前位置走到河的盡頭——如果可以，那么我們可以回傳，因為我們找到了所需的最少步數。 - 最后，如果
unreachable是True一旦這個回圈完成，這意味著我們不能達到使用Fibonacci數的任何位置，所以我們回傳-1。
通過這種方法，我獲得了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
uj5u.com熱心網友回復：
提高演算法性能的一些建議 -
- 如果
len(A) = 100000，您正在計算 100003 個斐波那契數，而我們只需要小于 100k 的斐波那契數，即 <30 個。 - 您的解決方案是
O(n^4)，因為每個X in reachablesorY in fibonaccis操作是O(N)whereNislen(A)。（和長度的fibonaccis是N因為上述問題的） - 由于您正在
item in list對fibonaccisand進行大量操作reachables，請考慮將其設為 aset或 adictionary以進行更快（O(1)而不是O(n)）查找。 - 即使有上述變化，演算法也會
O(N^2)因為嵌套回圈跨越A和reachables，所以你需要想出一個更好的方法。
對于您現有的實作，您需要遍歷所有路徑，然后最終您將獲得最少的跳轉次數。
而不是這種方法，如果您從 開始0，然后計算到目前為止您已經進行的跳躍次數，并保持每次跳躍后您可以到達多遠（以及達到哪些數字），那么您可以輕松找到最小跳躍次數需要到達終點。（這也將節省多余的作業，以防萬一您1在 A 中擁有所有s。
例如對于
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
所以你10在 3 次跳躍后到達了 end( )。
請在此處查看@nialloc 的答案 - https://stackoverflow.com/a/64558623/8677071似乎正在做類似的事情。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400688.html
上一篇：排序陣列中元素的天花板