算法经典面试题—斐波那契数列&爬楼梯

算法经典面试题—斐波那契数列&爬楼梯

算法经典面试题—斐波那契数列&爬楼梯

• 前言
• 一、爬楼梯
• • 题目描述
  • 题解
  • • 方法一：直接递归
    • 方法二：优化递归
    • 方法三：循环
• 二、斐波那契数列
• • 题目描述
  • 题解
  • • 方法一
    • 方法二
• 总结

---

前言

题目来源于：剑指 Offer 10- I. 斐波那契数列和力扣70. 爬楼梯

---

一、爬楼梯 题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
4.  1 阶 + 1 阶 + 1 阶
5.  1 阶 + 2 阶
6.  2 阶 + 1 阶

题解

分析：

    可以一次爬1阶或2阶
    所以可以将问题分为：只有1阶楼梯 || 只有两阶楼梯 || 有3阶以上的楼梯
    我们通过不断累加楼梯阶数得到规律，这里设楼梯阶数为n，爬到楼顶方法为m
    当n=1，m=1
    当n=2，m=2
    当n=3，m=1+2=3
    当n=4，m=2+3=5

    这里我们就能得到一个规律，当n>=3时，其方法为：(n-1)+(n-2)
    这复合递归的思想

方法一：直接递归

会超过时间限制，因为此时时间复杂度为o(n^2)

class Solution {
public:
    int climbStairs(int n) 
    {
           递归终止条件
        if(n==1) return 1;
        if(n==2) return 2;

        return climbStairs(n-1)+climbStairs(n-2);
    }
};

方法二：优化递归

  经过分析是因为递归解法中存在重复计算，那么我们可以减少重复计算，将计算的结果保存起来，再次有相关计算的时候，直接从缓存中读取。

class Solution {
public:
    unordered_map mp;
    int climbStairs(int n) 
    {
        if(n==1) return 1;
        if(n==2) return 2;

        vector fib(n+1,0);

        fib[1]=1;
        fib[2]=2;

        for(int i=3;i 
方法三：循环 
class Solution {
public:
    int climbStairs(int n) 
    {
        if(n==1) return 1;
        if(n==2) return 2;

        int res=0;//记录多少种方式

        int n1=1;
        int n2=2;

        for(int i=3;i<=n;i++)
        {
            res=n1+n2;
            n1=n2;
            n2=res;
        }
        return res;
    
    }
};
 
二、斐波那契数列 
题目描述 
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(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
 
 
题解 
  根据题目描述：
 
F(0)=0
F(1)=1
n>1时，F(n)=F(n-1) + F(n-2)
 
方法一 
  我们知道当n>1时，它的当前数值等于它上两个数之和，我们又知道F(0)和F(1)，所以我们可以从下向上循环迭代求解。
 
代码如下：
 
class Solution {
public:
    int fib(int n) 
    {
        if(n<2) return n;

        int mod=1e9+7;
        int res=0;

        int pre=1;
        int prepre=0;
        for(int i=2;i<=n;++i)
        {
            res=(pre+prepre)%mod;
            prepre=pre;
                pre=res;
        }
        return res;


    }
};

 
方法二 
  利用哈希表递归求解:
 
class Solution {
public:
    unordered_map mp;
    int fib(int n) 
    {
        if(n<2) return n;
        int mod=1e9+7;
        auto it=mp.find(n);
        if(it!=mp.end())
        {
            return (it->second)%mod;
        }
        int res=(fib(n-1)+fib(n-2))%mod;
        mp.insert(pair(n,res));
        return res;
    }
};
 
总结 
期待大家和我交流，留言或者私信，一起学习，一起进步！
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5697795.html