(lintcode)第336题斐波那契数列
要求:查找斐波纳契数列中第 N 个数
所谓的斐波纳契数列是指:前2个数是 0 和 1 ,第 i 个数是第 i-1 个数和第i-2 个数的和,斐波纳契数列的前10个数字是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …
样例
给定 1,返回 0
给定 2,返回 1
给定 10,返回 34
第一次想到的方法是使用递归,但是递归的效率比较低,时间超限,报错(代码运行时间超过了限制,检查你的时间复杂度。TLE通常是由死循环造成的,思考一下你的时间复杂度是否是最优的。)在这里也放上递归的代码(时间复杂度O(2^n)):
public class Solution { /* * @param n: an integer * @return: an ineger f(n) */ public int fibonacci(int n) { if(n==1){ return 0; }else if(n==2){ return 1; }else{ return fibonacci(n-1)+fibonacci(n-2); } }}
第二种方法就是把递归转化成为for循环来写,这样的话可以一定程度减少时间的复杂度,递归和for循环可以看成是两个互逆的过程。(时间复杂度O(n))总耗时: 2655 ms
public class Solution { /* * @param n: an integer * @return: an ineger f(n) */ public int fibonacci(int n) { if(n==1)//第一个直接返回 return 0; else if(n==2)//第二个直接返回 return 1; else if(n>=3){//大于等于3, int first=0,second=1; while(n>=3){ n--; int temp=second;//将第二个数的值保存 second=first+second;将第一个数和第二个数的和的值赋予second变量 first=temp;//将之前的第二个数的值赋予first变量 } return second; } else return 0; }}
当然,也可以使用数组来挨个存储每一个值。(时间复杂度O(n))
class Solution { public int fibonacci(int n) { if (n <= 1) { return 0; } int[] fib = new int[n]; fib[0] = 0; fib[1] = 1; for (int i = 2; i < n; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } return fib[n - 1]; }}
还有一种解法,是使用矩阵来求解,时间复杂度O(logn),斐波那契的递推公式可以表示成如下矩阵形式,KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ \begin{Bmatrix…KaTeX parse error: No such environment: equation* at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ =\begin{Bmatri…
矩阵是一个由m行n列元素排成的矩形阵列。矩阵长类似下面这样子,这是一个二阶矩阵,两行两列组成,里面的a,b,c,d就是它的元素: { a b c d } \begin{Bmatrix} a & b\\ c & d \end{Bmatrix} {acbd}
像下面这样的就是列向量,只有一列: { x 1 x 2 } \begin{Bmatrix} x_1\\ x_2 \end{Bmatrix} {x1x2}设KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲A=\begin{Bmatri…KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲X=\begin{Bmatri…则
KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲Y=AX= \begin{Bm…表示为二阶矩阵A与平面向量X的乘积。斐波那契(Fibonacci)数列,从第三项开始,每一项都是前两项之和。 F(n)=F(n − 1)+F(n − 2), n⩾3,把斐波那契数列中 相邻的两项F(n)和F(n − 1)写成一个2×1的矩阵。 F0=0 ,F1=1.KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ \begin{Bmatrix…KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ =\begin{Bmatri…KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ =\begin{Bmatri…KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ =\begin{Bmatri…KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ =\begin{Bmatri…KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ =\begin{Bmatri…那么求F(n)就等于求二阶矩阵KaTeX parse error: No such environment: equation* at position 7: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ \begin{Bmatrix…的n-1次方,结果是取矩阵第一行的第一列的元素,那么这个问题就转换成了二阶矩阵的n次幂,那么我们现在要求矩阵A的N次幂,首先二阶的矩阵乘法都满足结合律,如过A,B,C是任意的二阶矩阵,那么有A(BC)=(AB)C, A 6 = A 3 ∗ A 3 / / 用 了 三 次 乘 法 , 两 次 乘 法 计 算 出 A 3 , 最 后 一 次 乘 法 两 个 A 3 相 乘 A^{6}=A^{3}*A^{3}//用了三次乘法,两次乘法计算出A^{3},最后一次乘法两个A^{3}相乘 A6=A3∗A3//用了三次乘法,两次乘法计算出A3,最后一次乘法两个A3相乘 A 6 = A ∗ A ∗ A ∗ A ∗ A ∗ A / / 五 次 乘 法 , 直 接 六 个 A 相 乘 A^{6}=A*A*A*A*A*A//五次乘法,直接六个A相乘 A6=A∗A∗A∗A∗A∗A//五次乘法,直接六个A相乘还有一种方法,是转化成为2进制,比如6转化成为2进制就是110, A 6 = A 4 ∗ A 2 A^{6}=A^{4}*A^{2} A6=A4∗A2
(10进制)31 = (二进制) 11111 ,则 A 31 = A 16 ∗ A 8 ∗ A 4 ∗ A 2 ∗ A 1 A^{31}=A^{16}*A^{8}*A^{4}*A^{2}*A^{1} A31=A16∗A8∗A4∗A2∗A1
A N = A n ∗ A n 当 n 为 偶 数 A^{N}=A^{n}*A^{n}当n为偶数 AN=An∗An当n为偶数 A N = A n ∗ A n ∗ A 当 n 为 奇 数 A^{N}=A^{n}*A^{n}*A当n为奇数 AN=An∗An∗A当n为奇数
代码如下:
public class Solution { /* * @param n: an integer * @return: an ineger f(n) */ long[][]f=new long[][]{{1,1},{1,0}};//最初的数组 public int fibonacci(int n) { if(n==1)//为1时直接返回 return 0; else if(n==2||n==3)//为2,3的时候也直接返回 return 1; else if(n>3){//大于3的时候,记得n-2 f=power(n-2,f); return (int)f[0][0];//返回第一行的第一列的数 } else return 0; } public long[][] power(int n,long[][]f){ if(n==1) return f; if(n==2) return fun(f,f); if(n%2==0){ f=power(n/2,f); return fun(f,f); }else{ return fun(power(n/2,f),power(n/2+1,f)); } } public long[][] fun(long[][] f,long [][] m){//两个二阶矩阵相乘 long[][] temp = new long[2][2]; temp[0][0]=(f[0][0]*m[0][0]+f[0][1]*m[1][0]); temp[0][1]=(f[0][0]*m[0][1]+f[0][1]*m[1][1]); temp[1][0]=(f[1][0]*m[0][0]+f[1][1]*m[1][0]); temp[1][1]=(f[1][0]*m[0][1]+f[1][1]*m[1][1]); return temp; }}
还有一种直接求值得公式法,但是有不够准确的风险。
代码如下:
复制代码//直接求值法(利用公式F(n) = [@n/sqrt(5)]快速计算第n个斐波那契数) public static double fibonacci(int n){ double result = 0; double temp = Math.sqrt(5.0); result = (1/temp)*(Math.pow((1+temp)/2,n)-Math.pow((1-temp)/2, n)); return result; }
此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~
技术之路不在一时,山高水长,纵使缓慢,驰而不息。
公众号:秦怀杂货店
©著作权归作者所有:来自51CTO博客作者秦怀杂货店的原创作品,如需转载,请注明出处,否则将追究法律责任更多相关文章
- (lintcode)第454题 矩阵面积
- (lintcode)第28题 搜索二维矩阵
- 【递归】JavaScript实现99乘法表的编写(双层for循环与递归方法)
- 8.工厂方法
- Numpy
- 基于安全压缩感知的大数据隐私保护
- 图 - 邻接矩阵广度优先遍历(C语言)
- 图 - 邻接矩阵深度优先遍历(C语言)
- 深度学习可以不要乘法,北大、华为诺亚新论文:加法替代,效果不变,延迟