剑指10：斐波那契数列

传送门

nowcoder
leetcode

题目描述

两个栈实现一个队列，完成队列的 Push 和 Pop 操作。
队列中的元素为 int 类型。

C++ 代码 - nowcoder

/*
    状态表示：
        f[i] 表示斐波那契数列的第 i 项
    状态计算：
        f[i] = f[i - 1] + f[i - 2], i >= 2
    
    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution {
public:
    int Fibonacci(int n) {
        if (n <= 1) return n;
        
        int f[n + 1];
        f[0] = 0, f[1] = 1;
        for (int i = 2; i <= n; i ++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        return f[n];
    }
};

/*
    优化空间：三个变量保存元素，来回替换

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    int Fibonacci(int n) {
        if (n <= 1) return n;

        int first = 0, second = 1, third = 0;
        for (int i = 2; i <= n; i++) {
            third = first + second;
            first = second;
            second = third;
        }
    
        return third;
    }
};

C++ 代码 - leetcode

class Solution {
public:
    const int MOD = 1e9 + 7;

    int fib(int n) {
        if (n <= 1) return n;

        int f[n + 1];
        f[0] = 0, f[1] = 1; // base case
        for (int i = 2; i <= n; i ++) {
            f[i] = (f[i - 1] + f[i - 2]) % MOD;
        }
        return f[n];
    }
};


/*
    优化空间：三个变量保存元素
*/
class Solution {
public:
    const int MOD = 1e9 + 7;

    int fib(int n) {
        if (n <= 1) return n;

        int f0 = 0, f1 = 1, f2 = 0; // base case
        for (int i = 2; i <= n; i ++) {
            f2 = (f1 + f0) % MOD;
            f0 = f1;
            f1 = f2;
        }
        return f2;
    }
};