【杂题】Offer 10- I. 斐波那契数列-跟着帅地玩副业，开拓第二曲线PlayOffer

CrazyJavaBoy 永久会员 2023年3月24日上午10:45

时间复杂度: O(n) 空间复杂度O(1)

class Solution {
    //自底向上
    public int fib(int n) {
        if(n <= 1) {
            return n;
        }
        int a = 0;//a代表f(0)
        int b = 1;//b代表f(1)
        int c = 0;

        for(int i = 2; i <= n; i++) {
            //计算c
            c = (a + b) % 1000000007;
            //a b 往后走
            a = b;
            b = c;
        }
        return c;

    }
}

0 赞同 0 条回复

宁永久会员 2023年3月14日下午5:44

注意取模的问题

class Solution {
    public int fib(int n) {
        //动态规划递推，递归的方法时间复杂度太高
        if(n == 0 || n == 1){
            return n;
        }
        int f1 = 0, f2 = 1;
        int sum = 0;
        for(int i = 2; i <= n; i++){
            sum = (f1 + f2) % 1000000007;
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月17日下午11:37

迭代

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int a = 0, b = 1;
        while (n-- > 1) {
            int t = a;
            a = b;
            b += t;
            if (b >= 1000000007) b -= 1000000007;
        }
        return b;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年1月17日下午11:15

利用矩阵，需要注意取模精度

class Solution {

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

        int p = n-1;
        int [][] res= {{1,0},{0,1}};
        int [][]base = {{0,1},{1,1}};
        while(p>0) {
            if ((p &1) == 1) {
                res = multi(res, base);
            }

            base = multi(base, base);
            p>>=1;
        }
        return  res[1][1];
    }

    private int[][] multi(int[][] m1, int[][] m2) {
        int [][]res = new int[2][2];
        for(int i=0; i<2;i++){
            for(int j=0; j<2;j++){
                long tmp = (long)m1[i][0] * m2[0][j] + (long)m1[i][1] * m2[1][j];
                res[i][j] = (int)(tmp % 1000000007);
            }
        }
        return res;

    }
}

0 赞同 0 条回复

努力刷题普通 2022年12月5日上午5:20

时间复杂度：O(n), 空间复杂度：O(1)
class Solution(object):
class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        a, b = 0, 1
        for i in range(n):
            a, b = b, a+b
        return a%1000000007

0 赞同 0 条回复

T 普通 2022年12月3日上午10:01

下面代码

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

0 赞同 0 条回复

派大星普通 2022年12月2日下午11:01

class Solution {
//动态规划
    public int fib(int n) {
        if (n <= 1) return n;
        int MOD = (int)1e9 + 7;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2;i <= n;i++) {
            dp[i] = (dp[i-1]+dp[i-2]) % MOD;
        }
        return dp[n];
    }
}

0 赞同 0 条回复

y 普通 2022年12月2日下午5:03

var fib = function(n) {
   const MOD = 1000000007;
   const dp = [];
   dp[0] = 0;
   dp[1] = 1;
   for (let i = 2; i <= n; i++) {
       dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
   }
   return dp[n];
};

时间：O(n)

0 赞同 0 条回复

Tolkien 永久会员 2022年12月1日下午7:25

/**
     * 方法一：动态规划
     * 时间复杂度：O(n), 空间复杂度：O(n)
     * 1. 斐波那契数列的第i项为dp[i-1]
     * 2. dp[i] = dp[i-1] + dp[i-2]
     * 3. 由于关系式中需要i-1，i-2，当i=0，i=1时无法递推出结果，因此需要给dp[0], dp[1]赋值
     */
    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0; dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1]+dp[i-2]) % 1000000007;
        }

        return dp[n];
    }

    /**
     * 方法二：动态规划 优化
     * 时间复杂度：O(n), 空间复杂度：O(1)
     * 由于只运用前两个项，因此可以化简空间复杂度
     */
    public static int fib2(int n) {
        if (n <= 1) {
            return n;
        }

        int a = 0, b = 1, sum = 1;

        for (int i = 2; i < n; i++) {
            a = b;
            b = sum;
            sum = (a + b) % 1000000007;
        }

        return sum;
    }

    /**
     * 方法三：打表
     * 时间复杂度：O(range), 空间复杂度：O(n)
     * 每次测试一个样例，如n=36和84，都要从头往前计算，多少个样例计算多少次。
     * 若利用打表的话，只需要最开始的一次计算，每次测试只需从第一次计算中取
     */
    static int range = 101;
    static int[] cache = new int[range];

    static {
        cache[1] = 1;
        for (int i = 2; i < range; i++) {
            cache[i] = (cache[i - 1] + cache[i - 2]) % 1000000007;
        }
    }
    public static int fib3(int n) {
        return cache[n];
    }

    /**
     * 方法四：矩阵快速幂
     * 时间复杂度：O(logn), 空间复杂度：O(1)
     */
    // 矩阵幂计算
    static long[][] mul(long[][] a, long[][] b) {
        int x = a.length, y = b.length, z = b[0].length;
        long[][] ans = new long[x][z];

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < z; j++) {
                for (int k = 0; k < y; k++) {
                    ans[i][j] += (a[i][k] * b[k][j]) % 1000000007;
                }
            }
        }

        return ans;
    }
    public static int fib4(int n) {
        if (n <= 1) { return n; }

        long[][] mat = {{1, 1}, {1, 0}};
        long[][] ans = {{1}, {0}};

        // 通过快速幂计算矩阵的n-1次幂
        int x = n - 1;
        while (x != 0) {
            if ((x & 1) != 0) { ans = mul(mat, ans); }
            mat = mul(mat, mat);
            x >>= 1;
        }

        return (int)(ans[0][0] % 1000000007);
    }

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月30日下午11:40

动规

时间复杂度O(N)空间复杂度O(N)

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int MOD = (int)1e9 + 7;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2;i <= n;i++) {
            dp[i] = (dp[i-1]+dp[i-2]) % MOD;
        }
        return dp[n];
    }
}

优化，空间复杂度O(1)

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int MOD = (int)1e9 + 7;
        int a = 1,b = 0;
        for (int i = 2;i <= n;i++) {
            a = a + b;
            b = a - b;
            a %= MOD;
        }
        return a;
    }
}

0 赞同 0 条回复

青木普通 2022年11月30日下午11:21

/**
    没什么好说的
 */

class Solution {
    public int fib(int n) {
        // 递归会超时
        // if(n < 2) return n;
        // return (fib(n-1) + fib(n-2))%1000000007;

        if(n < 2) return n;
        int fn = 0, fn1 = 0, fn2 = 1;
        for(int i=2; i<=n; i++){
            fn = (fn1 + fn2) % 1000000007;
            fn1 = fn2;
            fn2 = fn;
        }
        return fn;
    }
}


/**
    快速幂又来了，真的强

    时间O(logn)
    空间O(1)
 */

class Solution {
    public int fib(int n) {
       if(n<2) return n;
       int[][] p = {{1,1},{1,0}};
       int[][] res = pow(p, n-1);
       return res[0][0];
    }

    public int[][] pow(int[][] p, int n){
        int[][] ret = {{1,0}, {0,1}};
        while(n > 0){
            if((n & 1) == 1) ret = multi(ret, p);
            n >>= 1;
            p = multi(p, p);
        }
        return ret;
    }

    public int[][] multi(int[][] a, int[][] b){
        int[][] ans = new int[2][2];
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                ans[i][j] = (int) (((long) a[i][0]*b[0][j] + (long) a[i][1]*b[1][j]) % 1000000007);
            }
        }
        return ans;
    }
}

0 赞同 0 条回复

Mooby 普通 2022年11月30日下午9:02

// 动态规划
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return c;
    }
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:34

class Solution {
public:
    int fib(int n) {// 使用动态规划，注意要对1e9+7取余
        if(n<2) return n;
        int p=0,q=0,r=1;
        int mod = 1000000007; 
        for(int i = 2; i <= n; i++){
            p = q;
            q = r;
            r = (p+q)%mod;
        }
        return r;
    }
};

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月30日下午8:17

时间复杂度O（n），空间复杂度O（1）

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

0 赞同 0 条回复

你有点可爱喔普通 2022年11月30日下午8:13

class Solution {
   static final int val = (int)(1e9+7);
    public int fib(int n) {
    //动态规划
        if(n < 2){
            return n;
        }
        int dp [] = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2;i <= n;i++){
            //取模
            dp[i] = dp[i-1] % val+dp[i-2] %val;
        }
        return dp[n] % val;
    }
}

0 赞同 0 条回复

【杂题】Offer 10- I. 斐波那契数列

共以下 15 个回答

迭代

# 回答此问题取消回复

【杂题】Offer 10- I. 斐波那契数列

共以下 15 个回答

迭代

# 回答此问题 取消回复

# 回答此问题取消回复