热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

剑指offer10斐波那契数列(递归、迭代、记忆化、数组四种方法)

描述大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项

描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。
n\leq 39n≤39
示例1
输入:
4
复制
返回值:
3

1、递归:效率低下

class Solution {
public:int Fibonacci(int n) {if (n == 0) {return 0;} if (n == 1) {return 1;}return Fibonacci(n - 1) + Fibonacci(n - 2);}
};```2、迭代法 最喜欢```cpp
class Solution {
public:int Fibonacci(int n) {if (n &#61;&#61; 0) {return 0;} if (n &#61;&#61; 1) {return 1;}int fistNumber &#61; 0;int SecondNumber &#61; 1;int result &#61; 0;for (int i &#61; 2; i <&#61; n; i&#43;&#43;) {result &#61; SecondNumber &#43; fistNumber;fistNumber &#61; SecondNumber;SecondNumber &#61; result;}return result;}
};&#96;&#96;&#96;3、动态规划&#xff0c;用个数组保存&#xff0c;但是需要额外的空间&#96;&#96;&#96;cpp
class Solution {
public:int Fibonacci(int n) {if (n &#61;&#61; 0) {return 0;} if (n &#61;&#61; 1) {return 1;}vector<int> result(n &#43; 1);result[0] &#61; 0;result[1] &#61; 1;for (int i &#61; 2; i <&#61; n; i&#43;&#43;) {result[i] &#61; result[i - 1] &#43; result[i - 2];}return result[n];}
};

4、记忆化数组&#xff0c;复杂&#xff0c;也不快啊

class Solution {
public:int Fibonacci(int n) {if (n &#61;&#61; 0) {return 0;} if (n &#61;&#61; 1) {return 1;}vector<int> result(n &#43; 1);result[0] &#61; 0;result[1] &#61; 1;for (int i &#61; 2; i <&#61; n; i&#43;&#43;) {result[i] &#61; result[i - 1] &#43; result[i - 2];}return result[n];}
};


推荐阅读
  • 开发笔记:9.八大排序
    开发笔记:9.八大排序 ... [详细]
  • PHP 过滤器详解
    本文深入探讨了 PHP 中的过滤器机制,包括常见的 $_SERVER 变量、filter_has_var() 函数、filter_id() 函数、filter_input() 函数及其数组形式、filter_list() 函数以及 filter_var() 和其数组形式。同时,详细介绍了各种过滤器的用途和用法。 ... [详细]
  • 本文详细介绍了网络存储技术的基本概念、分类及应用场景。通过分析直连式存储(DAS)、网络附加存储(NAS)和存储区域网络(SAN)的特点,帮助读者理解不同存储方式的优势与局限性。 ... [详细]
  • C语言标准及其GCC编译器版本
    编程语言的发展离不开持续的维护和更新。本文将探讨C语言的标准演变以及GCC编译器如何支持这些标准,确保其与时俱进,满足现代开发需求。 ... [详细]
  • 哈密顿回路问题旨在寻找一个简单回路,该回路包含图中的每个顶点。本文将介绍如何判断给定的路径是否构成哈密顿回路。 ... [详细]
  • 本文深入探讨了HTTP请求和响应对象的使用,详细介绍了如何通过响应对象向客户端发送数据、处理中文乱码问题以及常见的HTTP状态码。此外,还涵盖了文件下载、请求重定向、请求转发等高级功能。 ... [详细]
  • 本题探讨了在一个有向图中,如何根据特定规则将城市划分为若干个区域,使得每个区域内的城市之间能够相互到达,并且划分的区域数量最少。题目提供了时间限制和内存限制,要求在给定的城市和道路信息下,计算出最少需要划分的区域数量。 ... [详细]
  • 本文详细探讨了HTML表单中GET和POST请求的区别,包括它们的工作原理、数据传输方式、安全性及适用场景。同时,通过实例展示了如何在Servlet中处理这两种请求。 ... [详细]
  • 在现代Web应用中,当用户滚动到页面底部时,自动加载更多内容的功能变得越来越普遍。这种无刷新加载技术不仅提升了用户体验,还优化了页面性能。本文将探讨如何实现这一功能,并介绍一些实际应用案例。 ... [详细]
  • Ihaveastringwithquotesaroundthepathasfollows:我在路径周围有一个带引号的字符串,如下所示:C:\ProgramFiles(x ... [详细]
  • 本文详细介绍如何在Linux系统中配置SSH密钥对,以实现从一台主机到另一台主机的无密码登录。内容涵盖密钥对生成、公钥分发及权限设置等关键步骤。 ... [详细]
  • 给定行数 numRows,生成帕斯卡三角形的前 numRows 行。例如,当 numRows 为 5 时,返回的结果应为:[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]。 ... [详细]
  • 本文详细介绍了 org.apache.commons.io.IOCase 类中的 checkCompareTo() 方法,通过多个代码示例展示其在不同场景下的使用方法。 ... [详细]
  • 算法题解析:最短无序连续子数组
    本题探讨如何通过单调栈的方法,找到一个数组中最短的需要排序的连续子数组。通过正向和反向遍历,分别使用单调递增栈和单调递减栈来确定边界索引,从而定位出最小的无序子数组。 ... [详细]
  • 配置多VLAN环境下的透明SQUID代理
    本文介绍如何在包含多个VLAN的网络环境中配置SQUID作为透明网关。网络拓扑包括Cisco 3750交换机、PANABIT防火墙和SQUID服务器,所有设备均部署在ESXi虚拟化平台上。 ... [详细]
author-avatar
YOYO很快乐的傻瓜
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有