剑指 Offer 10- I. 斐波那契数列
题目:
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
范围: 0 <= n <= 100 的整数
一想到求斐波那契,就想到递归,啪,然后超时,因为递归效率实在太低,虽然代码简洁
所以递归不行,只能使用循环.
public static int fib(int n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); }
还有个问题,就是还需对结果进行1000000007取余,且往后结果远大于2的32次方,当然也会大于2的64次方,int和long都不够存储.
但是还有 BigDecimal，网上查了下据说可以存上千位的数，这十几二十位的数，当然小问题啦。
第100个斐波那契数:354,224,848,179,261,915,075
2的64次方: 18,446,744,073,709,551,616
方式一：使用BigDecimal数组
注意:1.数组长度可以动态定义,如果只需要第一项,却去定义长度100,多余
2.int类型转 BigDecimal类型 BigDecimal.valueOf(1)
3.相加用 add方法
4.divideAndRemainder 进行取余
返回一个数组: result[0]为商,result[1]为余
BigDecimal类型 转为 int类型 .intValue()
public static int fib1(int n) { int mod = 1000000007; //取余 int len = 101; BigDecimal[] arr = new BigDecimal[n+1]; arr[0] = BigDecimal.valueOf(0); arr[1] = BigDecimal.valueOf(1); //只计算到 arr[n] for (int i = 2; i < (n + 1); i++) { arr[i] = arr[i - 1].add(arr[i - 2]); //add 相加 } //divideAndRemainder 返回一个数组: result[0]为商,result[1]为余 BigDecimal[] result = arr[n].divideAndRemainder(BigDecimal.valueOf(mod)); return result[1].intValue(); //转为int返回 }
方式二:以减代取余 –>减法比取余效率更高
每当下一项大于1000000007时,就减去1000000007,所以即使最后相加,也不可能会产生大于两倍1000000007的数.这点很重要
初始化的int数组,所有项默认为0,所以
//arr[0] = 0; //可省–>默认值为0
public static int fib(int n) { int mod = 1000000007; //取余 int[] arr = new int[n + 1]; //arr[0] = 0; //可省-->默认值为0 arr[1] = 1; for (int i = 2; i < (n + 1); i++) { arr[i] = arr[i - 1] + (arr[i - 2]); //每当下一项大于mod时,减去mod,即相当于进行取余操作,以减法代替取余 效率更高 if (arr[i] > mod) { arr[i] -= mod; } } return arr[n]; }
方式三:以数组存储了并不需要的数,因为每次只需要第n个数,不需要对之前的结果进行存储. 以while 循环
public static int fib(int n) { if (n < 2) return n; int mod = 1000000007; //取余 int f = 0; //first int s = 1; //second int result = 0; //初始化结果 while (--n > 0) { result = f + s; if (result > mod) result -= mod; f = s; s = result; } return result; }
结果:
执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：35 MB, 在所有 Java 提交中击败了90.07% 的用户
通过测试用例：51 / 51
