LintCode | 366.Feibonacci

2019-11-06 07:58:00

字体：大中小

来源：转载

供稿：网友

查找斐波纳契数列中第 N 个数。所谓的斐波纳契数列是指：前2个数是 0 和 1 。第 i 个数是第 i-1 个数和第i-2 个数的和。斐波纳契数列的前10个数字是： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

快速矩阵幂解法

class Solution { public int fibonacci(int n) { Matrix bMatrix = new Matrix(1, 1, 1, 0); Matrix fMatrix = new Matrix(1, 0, 0, 1); while(n > 0) { if(n % 2 == 1) { fMatrix.multi(bMatrix); } bMatrix.multi(bMatrix); n /= 2; } return fMatrix.value[1][1]; }}class Matrix { int [][] value; Matrix(int a, int b, int c, int d) { value = new int[2][2]; value[0][0] = a; value[0][1] = b; value[1][0] = c; value[1][1] = d; } void multi(Matrix m){ int a = value[0][0]*m.value[0][0] + value[0][1]*m.value[1][0]; int b = value[0][0]*m.value[0][1] + value[0][1]*m.value[1][1]; int c = value[1][0]*m.value[0][0] + value[1][1]*m.value[1][0]; int d = value[1][0]*m.value[0][1] + value[1][1]*m.value[1][1]; value[0][0] = a; value[0][1] = b; value[1][0] = c; value[1][1] = d; }}

使用数组空间

空间复杂度为O(n)，用数组空间来换取计算结果

class Solution { public int fibonacci(int n) { if(n == 1) return 0; int [] feibonaqi = new int[n]; feibonaqi[0] = 0; feibonaqi[1] = 1; for(int i = 2; i < n; i++) { feibonaqi[i] = feibonaqi[i - 1] + feibonaqi[i - 2]; } return feibonaqi[n - 1]; }}

DP

class Solution { public int fibonacci(int n) { if(n == 1) return 0; if(n == 2) return 1; int [] dp = new int[3]; dp[1] = 1; for(int i = 2; i < n; i++) { dp[i%2] = dp[(i - 1)%2] + dp[(i - 2)%2]; } return dp[(n - 1)%2]; }}

还看到了与DP异曲同工的解法

class Solution { public int fibonacci(int n) { if(n == 1) return 0; if(n == 2) return 1; int first = 0; int second = 1; int third = 0; for(int i = 2; i < n; i++) { third = first + second; first = second; second = third; } return third; }}

上一篇：中国剩余定理理论

下一篇：杭电 2021 发工资

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注