博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
每日一算 -- 斐波那契数列类型题
阅读量:5749 次
发布时间:2019-06-18

本文共 1194 字,大约阅读时间需要 3 分钟。

前言

斐波那契数列定义

斐波那契数列指的是这样一个数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........ 这个数列从第3项开始,每一项都等于前两项之和

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。

日常找规律

  • 当有1阶时 F(1) = 1
  • 当有2阶时 F(2) = 2(可以1阶或者2阶)
  • 当有3阶时 F(3) = 3(可以1阶或者1、2阶或者2、1)
  • 当有4阶时 F(4) = 5(可以1阶或者1、2、1、1阶或2、1、1、1或2、2、1或2、1、2)
  • ...
  • 当有n阶时 F(n) = F(n - 1) + F(n - 2)
F(1)=1F(2)=2F(n)=F(n-1)+F(n-2)复制代码

实现方式

当我们得到推导公式,实现函数脑海里面会想到递归实现

递归

  • 时间复杂度: O(2^n)
function fiber (n) {    if ( n === 1) {        return 1    }    if ( n === 2) {        return 2    }    return fiber( n - 1) + fiber( n - 2 )}复制代码

循环

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)
function fiber (n) {  let step = []  step[1] = 1  if ( n >= 2) {      step[2] = 2  }  if ( n <= 2) {      return n  }  for ( let i = 3; i <= n; i++) {      step[i] =  step[i - 1] + step[i - 2]  }  return step[n]}复制代码

循环 + 优化空间复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)
function fiber (n) {  let prev1 = 1  let prev2 = 2  let result = 0  if ( n <= 2) {      return n  }  for ( let i = 3; i <= n; i++) {      result = prev1 + prev2      prev1 = prev2      prev2 = result  }  return result}复制代码

总结

转载于:https://juejin.im/post/5c99d47d6fb9a070ed53fdf6

你可能感兴趣的文章
Android 组件化/模块化之路——在展示层搭建MVP结构
查看>>
PostgreSQL 10.1 手册_部分 III. 服务器管理_第 31 章 逻辑复制_31.1. 发布
查看>>
详解 Kubernetes 的稳定性和可用性
查看>>
Python pyclamad病毒扫描与目录病毒扫描脚本(转载)
查看>>
斯坦福-随机图模型-week1.2_
查看>>
沃土前端社区Vue系列教程 - event bus 和 vuex
查看>>
JVM解读-方法区
查看>>
novawww9992019com18122221111 hypervisor接口添加host_ip字段
查看>>
《走出电商困局》读书笔记
查看>>
RocketMQ如何支持更多队列(翻译)
查看>>
Mysql +keepalived主从复制、主主复制(学习笔记十五)
查看>>
从“挖光缆”到“剪网线”|蚂蚁金服异地多活的微服务体系
查看>>
手机端如何实现压缩并上传多张图片,触屏图片压缩
查看>>
WPF自定义TabControl样式
查看>>
HBase高级用法
查看>>
redis开机启动脚本
查看>>
多线程提提速吧
查看>>
Eclipse怎么忽略掉报错的js文件
查看>>
GNOME Screencaster 将支持 Miracast P2P 传输
查看>>
P4 玩家 KALOOM从数据中心网络市场中脱颖而出
查看>>