尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情
本站主页面和blog页面暂时一样,目的是为了百度收录,百度收录之后,会将主页换回引导页~

站点信息

文章数目:195
已运行时间:
目录
  1. 509. 斐波那契数
  2. 509. 斐波那契数

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情
本站主页面和blog页面暂时一样,目的是为了百度收录,百度收录之后,会将主页换回引导页~

站点信息

文章数目:195
已运行时间:

509. 斐波那契数

class Solution {
    // TODO: for循环实现
    public int fib(int N) {
        if (N <= 1) return N;
        int first = 0;
        int second = 1;
        for (int i = 0; i < N - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }
//    // TODO: 递归实现O(2^n)
//    public int fib1(int n) {
//        if (n <= 1) return n;
//        return fib1(n - 1) + fib1(n - 2);
//    }
//    // TODO: 首尾实现
//    public int fib3(int n) {
//        if (n <= 1) return n;
//        int first = 0;
//        int second = 1;
//        while (n-- > 1) {
//            second += first;
//            first = second - first;
//        }
//        return second;
//    }
}

509. 斐波那契数

// 递归:O(2^n)
public static int fib1(int n) {
    if (n <= 1) return n;
    return fib1(n - 1) + fib1(n - 2);
}

// for循环:O(n)
public static int fib2(int n) {
    if (n <= 1) return n;
    int first = 0;
    int second = 1;
    for (int i = 0; i < n - 1; i++) {
        int sum = first + second;
        first = second;
        second = sum;
    }
    return second;
}
// 首尾法
public static int fib3(int n) {
    if (n <= 1) return n;

    int first = 0;
    int second = 1;
    while (n-- > 1) {
        second += first;
        first = second - first;
    }
    return second;
}
// 特征方程解法:O(1)
public static int fib4(int n) {
    double c = Math.sqrt(5);
    return (int) (Math.pow((1+c) / 2, n) - Math.pow((1-c) / 2, c));
}

博客内容遵循: 署名-非商业性使用-禁止演绎 4.0 国际(CC BY-NC-ND 4.0)

本文永久链接: https://www.wztlink1013.com/blog/pmd7dz/

编辑: 部署: 订阅:

评论区

Twikoo 转换 utterances

最新评论

Loading...