菲波那切数列(Fibonacci Number)
2024-10-07 22:34:00
什么是菲波那切数列？自己google一下，面试题里面经常遇到，考试递归算法用的。
在菲波那切数列中用递归不太好。第三种算法最好。
第一 递归算法最差了，不想说。测试一下，当N=6000时，半天出不来数据，有想砸电脑的冲动。
第二 数组 在N变大后，空间浪费严重。
第三 队列 最好 只使用2个队列的空间，时间复杂度O(1) 常数级。
1 递归算法 最差的算法 也是比较经典的 得会
class Solution {
public int fib(int N) {
if(N==1){
return 1;
}
if(N<=0){
return 0;
}
return fib(N-1)+fib(N-2);
}
}
2 使用数组 time:O(n) space:O(n)
class Solution {
public int fib(int N) {
if(N<=0){
return 0;
}
if(N<2){
return 1;
}
int[] nums=new int[N+1];
nums[0]=0;
nums[1]=1;
for(int i=2;i<N+1;i++){
nums[i]=nums[i-1]+nums[i-2];
}
return nums[N];
}
}
3. 使用队列 先进先出 time:O(n) space:O(1)
class Solution {
public int fib(int N) {
if(N<=0){
return 0;
}
if(N<2){
return 1;
}
Queue<Integer> queue=new LinkedList<>();
queue.offer(0);
queue.offer(1);
for(int i=2;i<N;i++){
queue.offer(queue.poll()+queue.peek());
}
return queue.poll()+queue.poll();
}
}
最新文章
- CS193P - 2016年秋 第一讲 课程简介
- queue
- 重构Web Api程序(Api Controller和Entity)续篇
- poj3295
- shell脚本之if语句
- spring3-hibernate3整合
- linux 病毒 sfewfesfs
- linux安装ruby
- 使用 Tomcat 7 新的连接池 —— Tomcat jdbc pool
- [jQuery] 使用jQuery printPage plugin打印其他頁面內容
- 功能和形式的反思sql声明 一个
- C++中printf和scanf的用法
- 微信小程序外包 就找北京动软 专业承接微信小程序定制
- docker 列出每个容器的IP
- 安装Python 库软件时提示"setuptools must be installed to install from a source distribution"错误
- html中&lt;a&gt;标签的种类
- web.config 加密/解密 正确版
- ABAP中不修改内表参照的结构，给内表/结构体增加字段
- easyui 获取特定页签tab
- 使用hibernate从一方获取多方信息时报错：org.hibernate.LazyInitializationException: failed to lazily initialize a collection of role