LeetCode | 面试题10- I. 斐波那契数列【剑指Offer】【Python】

LeetCode 面试题10- I. 斐波那契数列【剑指Offer】【Easy】【Python】【动态规划】

问题

力扣

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1

示例 2:

输入:n = 5
输出:5

提示:

  • 0 <= n <= 100

注意:本题与主站 509 题 相同。

思路

动态规划

fib(n) = fib(n - 1) + fib(n - 2)
注意,fib(n)会越界,所以最好是:
fib(n) % 1000000007 = (fib(n - 1) % 1000000007 + fib(n - 2) % 1000000007) % 1000000007
但是因为 Python 中整形数字的大小限制取决计算机的内存(可理解为无限大),因此可不考虑大数越界问题。

时间复杂度: O(n)

空间复杂度: O(1)

Python3代码
class Solution:
    def fib(self, n: int) -> int:
        dp_0, dp_1 = 0, 1
        for _ in range(n):
            dp_0, dp_1 = dp_1, dp_0 + dp_1
        return dp_0 % 1000000007

GitHub链接

Python

原文地址:https://www.cnblogs.com/wonz/p/12583168.html

时间: 03-26

LeetCode | 面试题10- I. 斐波那契数列【剑指Offer】【Python】的相关文章

面试题10:斐波那契数列

斐波那契数指的是这样一个数列:0.1.1.2.3.5.8.13.21.-- 这个数列从第三个数开始,之后的每一个数都由它前的两数相加得到. 我们知道在编程中我们可以用递归和迭代两种方法求指定的斐波那契数,但这两种方法各有利弊. 区别:递归法(时间复杂度O(2^n))写出来的代码可读性强,就相当于把书上的数学公式 翻译成代码,但这种方法效率太慢了,当你求第50个斐波那契数,你的电脑可能得运算十多分钟.而且递归很容易造成栈溢出,每调用一次函数就得开辟一块空间,而求第50个斐波那契数所调用函数的次数是

LeetCode | 面试题06. 从尾到头打印链表【剑指Offer】【Python】

LeetCode 面试题06. 从尾到头打印链表[剑指Offer][Easy][Python][链表] 问题 力扣 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回). 示例 1: 输入:head = [1,3,2] 输出:[2,3,1] 限制: 0 <= 链表长度 <= 10000 思路 解法一 reverse函数 时间复杂度: O(n),n为 head 链表长度. 空间复杂度: O(n),n为 head 链表长度. Python3代码 # Definition for si

剑指offer(10)—— 斐波那契数列以及跳台阶问题

总结 2^(n-1)可以用位移操作进行: 1<< (n-1) 如果递归不好思考的话,可以找规律,代码很简单 斐波那契数列(10) 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0). n<=39 public class Solution { public int Fibonacci(int n) { // 先判断n必须在范围内取值 if(n > 39 && n <= 0) return 0; // 为1直接返

JAVA基本算法面试题:1斐波纳契数列

开始学习JAVA,基础知识恶补! 斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1.1.2.3.5.8.13.21.……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*). 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 以下是Java代码实现(递归与递推两种方式): import java.util.Scanner;

10、斐波那契数列

要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0).n<=39 解法一:递归解法,但递归解法有很严重的效率问题,因为递归解法中重复的计算太多. 解法二:循环实现,避免重复计算,把已经得到的数列中间项保存起来. public class Solution { public int Fibonacci(int n) { if(n <= 0) return 0; if(n == 1) return 1; int a = 0, b = 1, sum = 0; for(int i

斐波那契数列(C++ 和 Python 实现)

(说明:本博客中的题目.题目详细说明及参考代码均摘自 "何海涛<剑指Offer:名企面试官精讲典型编程题>2012年") 题目 1. 写一个函数,输入 n, 求斐波那契(Fibonacci)数列的第 n 项.斐波那契数列的定义如下: 2. 一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级.求该青蛙跳上一个n级的台阶总共有多少种跳法? 3. 一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级,...... ,也可以跳上n级,此时该青蛙跳上一个 n 级的台阶共有多少种跳法

用递归方法计算斐波那契数列(Recursion Fibonacci Python)

先科普一下什么叫斐波那契数列,以下内容摘自百度百科: 斐波那契数列(Fibonacci sequence),又称黄金分割数列.因意大利数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,指的是这样一个数列:1.1.2.3.5.8.13.21.34...这个数列从第3项开始,每一项都等于前两项之和. 根据以上定义,用python定义一个函数,用于计算斐波那契数列中第n项的数字是多少: def fib_recur(n): if n==0 or n==1 : r

剑指offer编程题Java实现——面试题9斐波那契数列

题目:写一个函数,输入n,求斐波那契数列的第n项. 1 package Solution; 2 3 /** 4 * 剑指offer面试题9:斐波那契数列 5 * 题目:写一个函数,输入n,求斐波那契数列的第n项. 6 * 0, n=1 7 * 斐波那契数列定义如下:f(n)= 1, n=2 8 * f(n-1)+f(n-2), n>2 9 * @author GL 10 * 11 */ 12 public class No9Fibonacci { 13 14 public static void

斐波拉契数列的计算方法

面试题9.斐波拉契数列 题目: 输入整数n,求斐波拉契数列第n个数. 思路: 一.递归式算法: 利用f(n) = f(n-1) + f(n-2)的特性来进行递归,代码如下: 代码: long long Fib(unsigned int n) { if(n<=0) return 0; if(n==1) return 1; return Fib(n-1) + Fib(n-2); } 缺陷: 当n比较大时递归非常慢,因为递归过程中存在很多重复计算. 二.改进思路: 应该采用非递归算法,保存之前的计算结

斐波纳契数列

查找斐波纳契数列中第 N 个数. 所谓的斐波纳契数列是指: 前2个数是 0 和 1 . 第 i 个数是第 i-1 个数和第i-2 个数的和. 斐波纳契数列的前10个数字是: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... 样例 给定 1,返回 0 给定 2,返回 1 给定 10,返回 34 虽然这道题是一道入门级的题目,可是在第一遍做的时候并没有多想,直接使用的递归,然后数据通过95%,显示的到47的时候就溢出了.经过学习前辈的经验,该题的收获如下: 方法1:使用递归解,