[LintCode] Fibonacci

mykurisu 发布于2019-08-14 15:16 / 3454人阅读

摘要：时间浪费太多，不推荐。还可以用公式实现，我觉得就算了吧。

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 时间浪费太多，不推荐。

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

还可以用公式实现，我觉得就算了吧。

GPU云服务器云服务器 LintCode LintCode134_LRU Fibonacci 数学fibonacci

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65537.html

[LintCode] Climbing Stairs

摘要：无需动规，无需额外空间，等同于菲波那切数列。当然噜，也可以动规，记住就好。 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高级特性

摘要：常规的使用来统计一段代码运行时间的例子输出结果总结其实是一门特别人性化的语言，但凡在工程中经常遇到的问题，处理起来比较棘手的模式基本都有对应的比较优雅的解决方案。 python的高级特性名词与翻译对照表 generator 生成器 iterator 迭代器 collection 集合 pack/unpack 打包/解包 decorator 装饰器 context manager ...

yexiaobai 2019-07-30 14:19 评论0 收藏0
Python学习之路26-函数装饰器和闭包

摘要：初步认识装饰器函数装饰器用于在源代码中标记函数，以某种方式增强函数的行为。函数装饰器在导入模块时立即执行，而被装饰的函数只在明确调用时运行。只有涉及嵌套函数时才有闭包问题。如果想保留函数原本的属性，可以使用标准库中的装饰器。《流畅的Python》笔记本篇将从最简单的装饰器开始，逐渐深入到闭包的概念，然后实现参数化装饰器，最后介绍标准库中常用的装饰器。 1. 初步认识装饰器函数装饰...

sunny5541 2019-07-30 16:45 评论0 收藏0
javascript-函数表达式

摘要：函数表达式定义函数表达式区别于函数声明，也是一种定义函数的方式，形似与变量赋值，这个值就是函数体，例如函数表达式之匿名函数函数表达式之具名函数匿名函数之立即执行函数目前知道的是这三种形式，希望高人补充特点区别于函数声明，和普通变量一样使用前函数表达式定义：函数表达式区别于函数声明，也是一种定义函数的方式，形似与变量赋值，这个值就是函数体，例如： var a = function...

bingchen 2019-08-23 14:25 评论0 收藏0
斐波那契数列求和的js方案以及优化

摘要：在上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。动态规划解决方案斐波那契数列求和除了可以用递归的方法解决，还可以用动态规划的方法解决。在codewars上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。题目 function fibonacci(n) { if(n==0 || n == 1) r...

xinhaip 2019-08-20 11:35 评论0 收藏0