leetcode509. 斐波那契数(矩阵快速幂)
【摘要】 斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N,计算 F(N)。
示...
斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N,计算 F(N)。
示例 1:
输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2:
输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3:
输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3.
矩阵快速幂
-
class Solution {
-
int fib(int N) {
-
if (N <= 1) {
-
return N;
-
}
-
int[][] A = new int[][]{{1, 1}, {1, 0}};
-
matrixPower(A, N-1);
-
-
return A[0][0];
-
}
-
-
void matrixPower(int[][] A, int N) {
-
if (N <= 1) {
-
return;
-
}
-
matrixPower(A, N/2);
-
multiply(A, A);
-
-
int[][] B = new int[][]{{1, 1}, {1, 0}};
-
if (N%2 != 0) {
-
multiply(A, B);
-
}
-
}
-
-
void multiply(int[][] A, int[][] B) {
-
int x = A[0][0] * B[0][0] + A[0][1] * B[1][0];
-
int y = A[0][0] * B[0][1] + A[0][1] * B[1][1];
-
int z = A[1][0] * B[0][0] + A[1][1] * B[1][0];
-
int w = A[1][0] * B[0][1] + A[1][1] * B[1][1];
-
-
A[0][0] = x;
-
A[0][1] = y;
-
A[1][0] = z;
-
A[1][1] = w;
-
}
-
}
文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。
原文链接:fantianzuo.blog.csdn.net/article/details/105827421
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)