描述

查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指：

前2个数是 0 和 1 。

第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

在测试数据中第 N 个斐波那契数不会超过32位带符号整数的表示范围

样例

样例  1:
	输入:  1
	输出: 0
	
	样例解释: 
	返回斐波那契的第一个数字，是0.

样例 2:
	输入:  2
	输出: 1
	
	样例解释: 
	返回斐波那契的第二个数字是1.

编程语言：Java

解题思想：

1.使用泛型，因为使用数组一般需要预先定义大小。

2.注意物理索引和下标索引的区别

时间复杂度：O(n)

IDE代码如下：

package Lintcode_Naive;
 
import java.util.ArrayList;
import java.util.List;
 
public class _366 {
 
	public static void main(String[] args) {
		List<Integer> fibonacci = new ArrayList<Integer>();
		fibonacci.add(0);
		fibonacci.add(1);
		int number;
		for(int i=2;i<Long.SIZE;i++)
		{
			number=fibonacci.get(i-1)+fibonacci.get(i-2);
			fibonacci.add(number);
		}
		System.out.println(fibonacci.get(3));
	}
 
}
 

LintCode编辑器代码如下：

public class Solution {
    public int fibonacci(int n) {
        List<Integer> fibonacci = new ArrayList<Integer>();
		fibonacci.add(0);
		fibonacci.add(1);
		int number;
		for(int i=2;i<Long.SIZE;i++)
		{
			number=fibonacci.get(i-1)+fibonacci.get(i-2);
			fibonacci.add(number);
		}
		return fibonacci.get(n-1);  //下标索引=物理索引-1
    }
}