19. Custom Fibonacci Sequence

Origin: Custom Fibonacci Sequence

Given n (0-based indexing), return the n-th Fibonacci number where F(0) = 1, F(1) = 2, and F(n) = F(n-1) + F(n-2).

注意这不是标准斐波那契（标准的是 F(0)=0, F(1)=1），这题的起始值是 F(0)=1, F(1)=2。

Example 1

Input: n = 3

Output: 5

Explanation: F(0)=1, F(1)=2, F(2)=1+2=3, F(3)=2+3=5。

Example 2

Input: n = 10

Output: 144

Explanation: 前 11 个值：[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]。第 10 个（0-based）是 144。

Input Format

一个整数 n。

Constraints

• 0 <= n <= 92
• n is an integer

Output Format

返回一个整数：第 n 个斐波那契数。

Sample Input 0

0

Sample Output 0

1

Sample Input 1

1

Sample Output 1

2

---

函数契约

// 输入：n（整数，0-based 索引）
// 输出：第 n 个斐波那契数（F(0)=1, F(1)=2, F(n)=F(n-1)+F(n-2)）
// 边界：n=0 → 1；n=1 → 2；n=92 → 需要处理大数溢出

边界表

场景	返回什么
n = 0	1
n = 1	2
n = 92	最大值，注意 JS Number 精度
正常场景	F(n)

Resolution

我的解法

function getAutoSaveInterval(n) {
    let prepre = 1n
    let pre = 2n
    if (n === 0) return "1"
    if (n === 1) return "2"
    for (let i = 2; i <= n; i++) {
        let next = pre + prepre
        prepre = pre
        pre = next
    }
    return pre.toString()
}

TypeScript 技巧解法（来自评论区）

不换语言，用 @ts-ignore 绕过类型检查，配合解构赋值：

function getAutoSaveInterval(n: number): number {
    let [a, b] = [1, 2];
    if (n === 0) return a;
    if (n === 1) return b;
    for (let i = 2; i <= n; i++) {
        // @ts-ignore
        [a, b] = [BigInt(b), BigInt(a + b)]
    }
    return b;
}

[a, b] = [b, a + b] 是 Python 风格的解构赋值，一行完成交换和更新，比 let next = pre + prepre; prepre = pre; pre = next 更简洁。但混用了 Number 和 BigInt，a + b 在两者之间运算容易出问题，可读性不如全程 BigInt 的方案。

解题思路

斐波那契数列，起始值 F(0)=1, F(1)=2。迭代法用两个变量滚动，不需要数组，O(n) 时间 O(1) 空间。

踩坑经历

1. TypeScript 的 number 类型是 IEEE 754 双精度浮点数，最大安全整数是 2^53-1 ≈ 9×10^15。F(92) ≈ 7.5×10^19 超过安全范围，精度丢失导致 4 个大数用例失败。
2. TypeScript 模板返回值类型是 number，不支持返回 BigInt。
3. 换成 JavaScript（无类型约束），用 BigInt 计算，toString() 返回字符串，通过。
4. 题目函数签名标注返回 LONG_INTEGER，暗示结果可能超出普通整数范围，应该提前注意到。

复杂度

• 时间：O(n)，一次遍历
• 空间：O(1)，两个变量滚动

参考来源

• 相关文章：算法解题流程：从读题到提交的七步