Algorytmy JavaScript: rozwiąż ciąg Fibonacciego (LeetCode)

Liczby Fibonacciego , powszechnie oznaczane, F(n)tworzą ciąg zwany ciągiem Fibonacciego , w którym każda liczba jest sumą dwóch poprzednich, zaczynając od 0i 1. Liczby w następującym ciągu całkowitym 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

To jest

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Przykład 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

• 0 <= n <= 30

Istnieje kilka możliwości rozwiązania tego problemu: Metoda rekurencji.

Podejście rekurencji

Prosta metoda, która jest bezpośrednią rekurencyjną implementacją matematycznej relacji rekurencyjnej. Najwolniejszy sposób rozwiązania tego problemu, ponieważ wymaga wykładniczej złożoności czasowej : O(2^N) i złożoności przestrzennej : O(N) .

Programowanie dynamiczne z wykorzystaniem zapamiętywania (podejście odgórne)

Możemy uniknąć powtarzania pracy wykonywanej rekurencyjnie, przechowując obliczone do tej pory liczby Fibonacciego. Musimy tylko zapisać wszystkie wartości na mapie. Złożoność czasowa : O(N) i przestrzenna : O(N) .

Podejście iteracyjne

Iteracja, z rozwiązaniem wszystkich podproblemów i zwróceniem odpowiedzi dla elementu N, przy użyciu już obliczonych wartości Fibonacciego. Złożoność czasowa : O(N) i przestrzenna : O(N) .

Podejście iteracyjne ( zoptymalizowane pod względem przestrzeni)

Możemy zoptymalizować podejście iteracyjne przechowując poprzednie dwie liczby tylko dlatego, że to wszystko, czego potrzebujemy, aby uzyskać kolejną liczbę Fibonacciego w szeregu. Złożoność czasowa : O(N) i przestrzenna : O(1) .

Metoda potęgowania macierzy

Użyj potęgowania macierzy, aby uzyskać liczbę Fibonacciego z elementu w (0, 0) w wynikowej macierzy. Aby to zrobić, możemy polegać na równaniu macierzowym ciągu Fibonacciego, aby znaleźć N-tą liczbę Fibonacciego:

Jak działa ta formuła, możesz spojrzeć na Wiki

To rozwiązanie ma: złożoność czasową : O(logN) i przestrzenną : O(logN) .

Podejście matematyczne

Możemy skorzystać z golden ratio forumula:

Oto link , aby dowiedzieć się więcej o tym, jak działa ciąg Fibonacciego i złoty podział.

To rozwiązanie ma: złożoność czasową : O(logN) i przestrzenną : O(1) .

Ponadto czasami wymagane jest zwrócenie nie wartości dla danego N, ale zwrócenie tablicy elementów Fibonacciego aż do danego N.

Przykład:

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

oraz programowanie dynamiczne z wykorzystaniem zapamiętywania z niewielkimi zmianami:

Rozważaliśmy różne opcje rozwiązania problemu Fibonacciego, najtrudniejszym do zrozumienia jest potęgowanie macierzowe, ale zazwyczaj znajomość 4 poprzednich metod wystarcza na rozmowę kwalifikacyjną.

Mam nadzieję, że było to dla Ciebie przydatne!

Dziękuje za przeczytanie! Do zobaczenia wkrótce.

Więcej treści na PlainEnglish.io . Zapisz się do naszego bezpłatnego cotygodniowego biuletynu . Śledź nas na Twitterze , LinkedIn , YouTube i Discordzie . Zainteresowany Growth Hackingiem? Sprawdź obwód .