Einfach 3 gelöst 100.0% Erfolgsquote

Fibonacci Number

Return the n-th Fibonacci number.

Das lernst du

  • Generate a sequence from its previous terms
  • Update two variables at once
  • See why naive recursion is slow

Problem

Übersetzung anzeigen

The Fibonacci sequence starts 0, 1 and each next number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, …. F(0) = 0 and F(1) = 1.

Implement fibonacci(n).

Input

n: The position in the sequence.

Output

Return F(n).

Einschränkungen

0 ≤ n ≤ 90

Beispiele

Beispiel 1
Eingabe:
n = 10

Erwartete Ausgabe:
expected = 55
Eingabe:
long long n = 10;

Erwartete Ausgabe:
long long expected = 55;
Eingabe:
long n = 10;

Erwartete Ausgabe:
long expected = 55;

Erläuterung

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.

Beispiel 2
Eingabe:
n = 0

Erwartete Ausgabe:
expected = 0
Eingabe:
long long n = 0;

Erwartete Ausgabe:
long long expected = 0;
Eingabe:
long n = 0;

Erwartete Ausgabe:
long expected = 0;

Erläuterung

By definition F(0) = 0.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

The first two values are fixed, so start from the base cases.

Hinweis 2

Build later values from the two previous ones instead of recomputing recursively.

Hinweis 3

Use an iterative approach to avoid repeated work and deep recursion.

Erwartete Komplexität

O(n) time, O(1) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 HJhettory Jurash Python 774 ms - 4/5 Code ansehen
2 KKKaneki Ken Python 858 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 2 vollständige Lösungen unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.