iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 22
0
自我挑戰組

Leetcode新手挑戰30天系列 第 22

#509 Fibonacci Number - 研究其他解法

前情提要

因為昨天submit後,時間和空間的結果都很差,仔細想了想應該是因為遞迴的關係,所以今天想來研究下其他人的寫法

進入正題

在參考1連結中,雖然不是使用python語言,但提供了很多種解法的思路,除了遞迴的方式之外,還有另外3種解法:
1.建立一個陣列,用陣列紀錄所有計算過的費波那契數
2.用變數的方式記錄前兩個費波那契數
3.因為這題leetcode題目中有提到輸入的數字範圍,所以直接hardcode範圍內的費波那契數
因為我很好奇這三種方法在submit後的時間和空間的結果上可以進步多少,所以我用了他提供的解法邏輯寫:

-陣列的方式

def fib(self, N: int) -> int:
    Fibo=[0,1]
    for i in range(2, N+1):
        Fibo.append(Fibo[i-1] + Fibo[i-2])
    return Fibo[N]

結果
https://ithelp.ithome.com.tw/upload/images/20190923/201133933tuVvhLbJx.png

-變數的方式

def fib(self, N: int) -> int:
    if N < 2:
        return N
    previous1 = 0
    previous2 = 1
    for i in range(2, N+1):
        sum = previous1 + previous2
        previous1 = previous2
        previous2 = sum
    return previous2

結果
https://ithelp.ithome.com.tw/upload/images/20190923/20113393f9ks7t0kNu.png

-Hardcode

def fib(self, N: int) -> int:
    Fibo=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]
    return Fibo[N]

結果
https://ithelp.ithome.com.tw/upload/images/20190923/201133933KkhoQdMLR.png

比較表:
https://ithelp.ithome.com.tw/upload/images/20190923/201133934aJeTU8KOG.png
從上面runtime和memory的結果上來看,用變數的方式兩種都是最少的,這個應該是和時間複雜度和空間複雜度的計算有相關,明天來研究這個.

參考資料

參考1[LeetCode] Fibonacci Number 斐波那契数字


上一篇
#509 Fibonacci Number - 繼續解
下一篇
Day 23 時間複雜度與空間複雜度
系列文
Leetcode新手挑戰30天31

尚未有邦友留言

立即登入留言