斐波那契数
难度:
标签:
题目描述
代码结果
运行时间: 36 ms, 内存: 14.7 MB
/*
* 思路：
* 使用Java Stream API来生成斐波那契数列。
* 我们可以利用Stream.iterate方法来生成一个无限流，然后通过限制流的大小来得到第n个斐波那契数。
*/
import java.util.stream.Stream;
public class FibonacciStream {
public int fib(int n) {
return Stream.iterate(new int[]{0, 1}, f -> new int[]{f[1], f[0] + f[1]})
.limit(n + 1)
.map(f -> f[0])
.reduce((a, b) -> b)
.orElse(0);
}
}解释
方法:
该题解实现了斐波那契数列的计算，采用迭代方法而非递归。定义两个变量a和b，初始值分别为0和1，对应斐波那契数列的F(0)和F(1)。在每次迭代中，将b的值赋给a，而b的新值为a和b之前的和，这样连续迭代n次后，a的值即为F(n)。这种方法避免了递归调用的重复计算，提高了效率。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在迭代求解斐波那契数时，选择使用两个变量a和b而不是使用数组来存储所有计算过的斐波那契数？
▷🦆
在迭代过程中，将b的值赋给a，然后将a+b的结果赋给b，这种操作是否有可能在某些编程环境下导致数值溢出？
▷🦆
该迭代方法在n=0的情况下是否直接返回正确答案，还是需要进行特殊处理？
▷🦆
如果需要计算非常大的斐波那契数（例如n=10000），这种迭代方法是否还适用，或者需要考虑其他算法优化？
▷相关问题
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示：
1 <= n <= 45
将数组拆分成斐波那契序列
给定一个数字字符串 num，比如 "123456579"，我们可以将它分成「斐波那契式」的序列 [123, 456, 579]。
形式上，斐波那契式 序列是一个非负整数列表 f，且满足：
0 <= f[i] < 231，（也就是说，每个整数都符合 32 位 有符号整数类型）f.length >= 3- 对于所有的
0 <= i < f.length - 2，都有f[i] + f[i + 1] = f[i + 2]
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
返回从 num 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
示例 1：
输入：num = "1101111" 输出：[11,0,11,11] 解释：输出[110,1,111]也可以。
示例 2：
输入: num = "112358130" 输出: [] 解释: 无法拆分。
示例 3：
输入："0123" 输出：[] 解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
提示：
1 <= num.length <= 200num中只含有数字
最长的斐波那契子序列的长度
如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
n >= 3- 对于所有
i + 2 <= n，都有X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例 1：
输入: arr = [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
示例 2：
输入: arr = [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
提示：
3 <= arr.length <= 1000-
1 <= arr[i] < arr[i + 1] <= 10^9