Java实现 LeetCode 509 斐波那契数
2023-09-14 08:58:04 时间
509. 斐波那契数
斐波那契数,通常用 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.
提示:
0 ≤ N ≤ 30
PS:
第一个比较简单,
第二个是用黄金分割求斐波那契
第三个是矩阵求斐波那契
class Solution {
public int fib(int N) {
// if (N == 0 || N == 1) {
// return N;
// }
// int x = 0,y = 1,z = 1,i = 0,end = N-2;
// while (i <= end) {
// z = x + y;
// x = y;
// y = z;
// i++;
// }
// return z;
// double goldenRatio = (1 + Math.sqrt(5)) / 2;
// return (int)Math.round(Math.pow(goldenRatio, N)/ Math.sqrt(5));
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;
}
}
相关文章
- Java实现 LeetCode 757 设置交集大小至少为2(排序+滑动窗口)
- Java实现 LeetCode 669 修剪二叉搜索树(遍历树)
- Java实现 LeetCode 507 完美数
- Java实现 LeetCode 470 用 Rand7() 实现 Rand10()
- Java实现 LeetCode 475 供暖器
- Java实现 LeetCode 474 一和零
- Java实现 LeetCode 449 序列化和反序列化二叉搜索树
- Java实现 LeetCode 436 寻找右区间
- Java实现 LeetCode 412 Fizz Buzz
- Java实现 LeetCode 381 O(1) 时间插入、删除和获取随机元素 - 允许重复
- Java实现 LeetCode 377 组合总和 Ⅳ
- Java实现 LeetCode 368 最大整除子集
- Java实现 LeetCode 316 去除重复字母
- Java实现 LeetCode 299 猜数字游戏
- Java实现 LeetCode 230 2的幂
- Java实现 LeetCode 223 矩形面积
- Java实现 LeetCode 208 实现 Trie (前缀树)
- Java实现 LeetCode 190 颠倒二进制位
- Java实现 LeetCode 146 LRU缓存机制
- Java实现 LeetCode 142 环形链表 II(二)
- Java实现 LeetCode 139 单词拆分
- Java实现 LeetCode 120 三角形最小路径和
- Java实现 LeetCode 96 不同的二叉搜索树
- Java实现 LeetCode 35 搜索插入位置
- Java实现 LeetCode 14 最长公共前缀
- Java实现 LeetCode 20 有效的括号
- Java实现LeetCode_0009_PalindromeNumber
- Java实现LeetCode_0026_RemoveDuplicatesFromSortedArray
- Atitit web httphandler的实现 java python node.js c# net php 目录 1.1. Java 过滤器 servelet1 1.2. Python的
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点