LeetCode_509.斐波那契数
2024-10-07 07:23:50
LeetCode-cn_509
斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N,计算 F(N)。
示例 1:
输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2:
输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3:
输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3.
提示:
0 ≤ N ≤ 30
方法一:递归方法题解
- 测试用例:31(0~30)
- 执行用时:18ms
- 内存消耗:33.4MB
class Solution {
public int fib(int N) {
if (N < 2) return N;
return fib(N-1) + fib(N-2);
}
}
方法二:动态编程方法题解
- 测试用例:31(0~30)
- 执行用时:1ms
- 内存消耗:33.8MB
class Solution {
public int fib(int N) {
if (N < 2) return N;
int[] fib = new int[N+1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= N; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[N];
}
}
方法三:矩阵幂方法题解
- 测试用例:31(0~30)
- 执行用时:1ms
- 内存消耗:33.5MB
class Solution {
public int fib(int N) {
if (N < 2) return N;
int F[][] = new int[][] { { 1, 1 }, { 1, 0 } };
power(F, N - 1);
return F[0][0];
}
void power(int F[][], int N) {
int M[][] = new int[][] { { 1, 1 }, { 1, 0 } };
for (int i = 2; i <= N; i++) {
mutiply(F, M);
}
}
void mutiply(int F[][], int M[][]) {
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
}
方法四:优化空间复杂度为 O(1) 题解
- 测试用例:31(0~30)
- 执行用时:0ms
- 内存消耗:33.3MB
class Solution {
public int fib(int N) {
if (N < 2) return N;
int a = 0, b = 1, c;
for (int i = 2; i <= N; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
}
最新文章
- 10.Configure One-to-Many(配置一对多关系)【Code-First系列】
- oracle SQLPLUS 常用set设置
- mormot json操作
- mysql分库分表
- TNF-mutithread 编译过程记录
- HDOJ2021发工资咯:)
- 转:如何在Linux上提高文本的搜索效率
- sdut-2725-The Urge to Merge-状压DP
- 表格布局TableLayout
- WPF MVVM使用prism4.1搭建
- linux 的一些脑洞操作
- Hadoop学习笔记1:伪分布式环境搭建
- QT出现应用程序无法正常启动0xc000007b的错误
- Linux操作系统df相关问题解惑
- Effective Java 第三版——89. 对于实例控制,枚举类型优于READRESOLVE
- app:processDebugResources
- android打印日志封装
- OpenGL和D3D11中的深度模版测试
- 测试SQL
- Rails 5 Test Prescriptions 倒数第2章spring gem 如何让测试变快。分离rails(只有原理)
热门文章
- 05.AutoMapper 之配置验证(Configuration Validation)
- vue项目1-pizza点餐系统4-二级、三级路由
- kickstart一键装机部署
- VMware虚拟机中的CentOS7安装Nginx后本机无法访问的解决办法
- for 循环,range()函数和导入模块
- Python之网路编程之死锁,递归锁,信号量,Event事件,线程Queue
- Python开发WebService:REST,web.py,eurasia,Django
- java面向对象1-面向对象概念
- java redirect用法
- 在centos7.5使用DockerFile构建镜像时报错“Error parsing reference: ";microsoft/dotnet:2.2-aspnetcore-runtime AS base"; is not a valid repository/tag: invalid reference format”