Решение за число на Фибоначи LeetCode

Ниво на трудност Лесно
Често задавани в Кирпич Амазонка ябълка Bloomberg иБей Facebook Goldman Sachs Google Infosys JPMorgan Математика Microsoft Nvidia Оракул SAP Uber VMware Zillow
ZoomПрегледи 215

Декларация за проблема

Число на Фибоначи LeetCode Solution – „Числото на Фибоначи“ посочва, че The числа на Фибоначи, обикновено означавано F(n) образуват последователност, наречена Последователност на Фибоначи, така че всяко число е сумата от двете предходни, като се започне от 0 и 1, Това е,

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

даден n, изчисли F(n).

Решение за число на Фибоначи LeetCode

Пример 1:

Вход:

 n = 2

Изход:

 1

Обяснение:

 F(2) = F(1) + F(0) = 1 + 0 = 1.

Пример 2:

Вход:

 n = 3

Изход:

 2

Обяснение:

 F(3) = F(2) + F(1) = 1 + 1 = 2.

Пример 3:

Вход:

 n = 4

Изход:

 3

Обяснение:

 F(4) = F(3) + F(2) = 2 + 1 = 3.

Подход

Идея:

Основното наблюдение е, че всяко F(i) зависи от сбора от F(i-1) и F(i-2). По този начин можем да вземем две променливи, които ще съхраняват първоначалната стойност, след което ще повторим до N, за да получим резултата.

обяснение

  • N==0: връщане на 0
  • N==1: връщане на 1
  • по подразбиране: връщане на fib(N-1) + fib(N-2)

нека поговорим за втори подход:

Разглеждайки последователността на [34,55,89] можем да видим a модел това е, ако разделим всеки два последователни члена, делене води до идентичен брой близо до 1.618 наречен златно съотношение. Наистина имаме формулата за това! Наречен Формулата на Бине.

Добре? как можем да използваме това златно нещо! 34 е 9 термин, Ако намерим pow(golden,Nth term)/sqrt(5) заграден с a закръглят функция, ще получим стойността на N-тия член O(1) време и пространство!

код

C++ код на числото на Фибоначи

class Solution {
public:
    int fib(int n) {
        if(n==0)
            return 0;
        if (n==1)
            return 1;
        int a=0,b=1,c;
        for(int i=1;i<n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
        
    }
};

JAVA програма за число на Фибоначи

class Solution {
    public int fib(int n) {
        if(n==0)
            return 0;
        if (n==1)
            return 1;
        int a=0,b=1,c=0;
        
        for(int i=1;i<n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
        
    }
}

Анализ на сложността за решение на числото на Фибоначи LeetCode

Сложност във времето

НА)

Сложност на пространството

O (1)

Translate »