主题
11. 旋转数组的最小数字
来源
https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
题目
写一个函数,输入 n
,求斐波那契(Fibonacci)数列的第 n
项。斐波那契数列的定义如下:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例:
示例 1.
输入:n = 2
输出:1
示例 2.
输入:n = 5
输出:5
提示:
- 0 <= n <= 100
思路
斐波那契数列 f(n) = f(n-1) + f(n-2)
最简单的解法是
js
const fib = (n) => (n <= 1 ? n : fib(n - 1) + fib(n - 2));
10
/ \
9 8
/ \ / \
8 7 7 6
/ \ / \ / \ / \
7 8 6 5 6 5 5 4
这样时间复杂度是 O(n²),随着 n 越大递归的速度就越慢,有越来越多重复的计算。
我们反过来,发现规律是每行的结果,都是用之前的的两个结果相加,这样就没有重复的计算了。
f(2) = f(1) + f(0)
f(3) = f(2) + f(1)
f(4) = f(3) + f(2)
...
f(n) = f(n-1) + f(n-2)
10
/
9
/ \
8 7
/ \ / \
7 8 6 5
我们得到了时间复杂度为 O(logn) 的解法,动态规划。
解题
js
/**
* @param {number} n
* @return {number}
*/
var fib = function (n) {
if (n <= 1) return n;
let a = 0;
let b = 1;
let x = 1000000007; // 题目要求
let res = 0;
for (var i = 2; i <= n; i++) {
res = a + b;
res = res <= x ? res : res % x; // 题目要求
a = b;
b = res;
}
return res;
};
题目 2
青蛙跳台阶问题
题目
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例:
示例 1.
输入:n = 2
输出:2
示例 2.
输入:n = 7
输出:21
提示:
- 0 <= n <= 100
思路
稍微分析一下,此题跟斐波那契数列几乎一样,除了 f(0) = 1,把上题稍微修改一下即可。
解题
js
/**
* @param {number} n
* @return {number}
*/
var numWays = function (n) {
if (n <= 1) return 1;
let a = 1;
let b = 1;
let x = 1000000007; // 题目要求
let res = 0;
for (var i = 2; i <= n; i++) {
res = a + b;
res = res <= x ? res : res % x; // 题目要求
a = b;
b = res;
}
return res;
};
从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch