LeetCode------斐波那契数列(2)
2024-10-20 18:57:33
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
写一个函数,输入 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
第一种解法:
将每次计算出来的结果存入hashmap中
class Solution {
private Map<Integer,Integer> storgefib =new HashMap<>();
public int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
if(null != storgefib.get(n)){
return storgefib.get(n);
}else{
int result = (fib(n-1)+fib(n-2))%1000000007;
storgefib.put(n,result);
return result;
}
}
}
第二种方式,从底部向上。使用循环求解
class Solution {
public int fib(int n){
int result = 0;
int pre = 1;
int prePre =0;
if(n == 0) return 0;
if(n == 1) return 1;
if(n >= 2){
for(int i = 2;i <= n; i++){
result = (pre+prePre)%1000000007;
prePre = pre;
pre = result;
}
}
return result;
}
}
解答过程同爬楼梯:具体参考这里:https://blog.csdn.net/weixin_43304253/article/details/122269352
最新文章
- redis 基础知识
- content相关属性
- LeetCode Moving Average from Data Stream
- 一道javascript面试题
- Apache HttpClient使用之阻塞陷阱
- [mysql] linux 下mysql 5.7.12 安装
- Introduction to Financial Management
- Ubuntu下设置Tomcat成为服务(开机启动)
- Poem: Reserverd Words
- Android应用开发基础篇(1)-----Button
- 外部SRAM实验,让STM32的外部SRAM操作跟内部SRAM一样(转)
- 图论算法-Tarjan模板 【缩点;割顶;双连通分量】
- SAP如何修改表的数据
- LAD 线性判别分析
- 小Q系列故事——屌丝的逆袭
- easyui combobox 去空格事件 去掉,结果输入空格体验不畅的感觉,让combobox能够输入空格
- ABP框架系列之二十八:(Handling-Exceptions-异常处理)
- HDU 1171 01背包
- 正交表和TCG的使用
- ubuntu 18.04下安装配置Hue问题记录
热门文章
- google nexus5x 刷机抓包逆向环境配置(一)
- Redis 05 集合
- JavaScript的入门
- jQuery使用case记录
- Taurus.MVC-Java 版本打包上传到Maven中央仓库(详细过程):3、Maven独立插件安装与settings.xml配置
- Windows DNS服务器的子网掩码排序
- Skype for Business server 数据库安装
- MySQL5.7.15数据库配置主从服务器实现双机热备实例教程
- Kubernetes 监控--Alertmanager
- 5.Ceph 基础篇 - 认证