什么是菲波那切数列？自己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();
}
}