[LintCode] Fibonacci

mykurisu 發(fā)布于2019-08-14 15:16 / 3514人閱讀

摘要：時間浪費(fèi)太多，不推薦。還可以用公式實(shí)現(xiàn)，我覺得就算了吧。

Problem

Find the Nth number in Fibonacci sequence.

A Fibonacci sequence is defined as follow:

The first two numbers are 0 and 1.
The i th number is the sum of i-1 th number and i-2 th number.
The first ten numbers in Fibonacci sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

Solution

class Solution {
    public int fibonacci(int n) {
        int[] f = new int[n + 2];
        f[1] = 0;
        f[2] = 1;
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}

class Solution {
    public int fibonacci(int n) {
        if (n < 3) return n - 1;
        int first = 0;
        int second = 1;
        int third = 1; //its value doesn"t matter 
        for (int i = 3; i <= n; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }
}

Recuision 時間浪費(fèi)太多，不推薦。

class Solution {
    public int fibonacci(int n) {
        if (n == 1) return 0;
        if (n == 2) return 1;
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

還可以用公式實(shí)現(xiàn)，我覺得就算了吧。

GPU云服務(wù)器云服務(wù)器 LintCode LintCode134_LRU Fibonacci 數(shù)學(xué)fibonacci

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/65537.html

相關(guān)文章

[LintCode] Climbing Stairs

摘要：無需動規(guī)，無需額外空間，等同于菲波那切數(shù)列。當(dāng)然嚕，也可以動規(guī)，記住就好。 Problem You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you ...

jemygraw 2019-08-14 15:28 評論0 收藏0
python高級特性

摘要：常規(guī)的使用來統(tǒng)計(jì)一段代碼運(yùn)行時間的例子輸出結(jié)果總結(jié)其實(shí)是一門特別人性化的語言，但凡在工程中經(jīng)常遇到的問題，處理起來比較棘手的模式基本都有對應(yīng)的比較優(yōu)雅的解決方案。 python的高級特性名詞與翻譯對照表 generator 生成器 iterator 迭代器 collection 集合 pack/unpack 打包/解包 decorator 裝飾器 context manager ...

yexiaobai 2019-07-30 14:19 評論0 收藏0
Python學(xué)習(xí)之路26-函數(shù)裝飾器和閉包

摘要：初步認(rèn)識裝飾器函數(shù)裝飾器用于在源代碼中標(biāo)記函數(shù)，以某種方式增強(qiáng)函數(shù)的行為。函數(shù)裝飾器在導(dǎo)入模塊時立即執(zhí)行，而被裝飾的函數(shù)只在明確調(diào)用時運(yùn)行。只有涉及嵌套函數(shù)時才有閉包問題。如果想保留函數(shù)原本的屬性，可以使用標(biāo)準(zhǔn)庫中的裝飾器。《流暢的Python》筆記本篇將從最簡單的裝飾器開始，逐漸深入到閉包的概念，然后實(shí)現(xiàn)參數(shù)化裝飾器，最后介紹標(biāo)準(zhǔn)庫中常用的裝飾器。 1. 初步認(rèn)識裝飾器函數(shù)裝飾...

sunny5541 2019-07-30 16:45 評論0 收藏0
javascript-函數(shù)表達(dá)式

摘要：函數(shù)表達(dá)式定義函數(shù)表達(dá)式區(qū)別于函數(shù)聲明，也是一種定義函數(shù)的方式，形似與變量賦值，這個值就是函數(shù)體，例如函數(shù)表達(dá)式之匿名函數(shù)函數(shù)表達(dá)式之具名函數(shù)匿名函數(shù)之立即執(zhí)行函數(shù)目前知道的是這三種形式，希望高人補(bǔ)充特點(diǎn)區(qū)別于函數(shù)聲明，和普通變量一樣使用前函數(shù)表達(dá)式定義：函數(shù)表達(dá)式區(qū)別于函數(shù)聲明，也是一種定義函數(shù)的方式，形似與變量賦值，這個值就是函數(shù)體，例如： var a = function...

bingchen 2019-08-23 14:25 評論0 收藏0
斐波那契數(shù)列求和的js方案以及優(yōu)化

摘要：在上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實(shí)現(xiàn)。動態(tài)規(guī)劃解決方案斐波那契數(shù)列求和除了可以用遞歸的方法解決，還可以用動態(tài)規(guī)劃的方法解決。在codewars上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實(shí)現(xiàn)。題目 function fibonacci(n) { if(n==0 || n == 1) r...

xinhaip 2019-08-20 11:35 評論0 收藏0