509. 斐波那契数(Fibonacci Number)E
英文题目
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), for N > 1.Given N, calculate F(N).
Example 1:
Input: 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.Example 2:
Input: 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.Example 3:
Input: 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.Note:
0 ≤ N ≤ 30.
中文题目
斐波那契数，通常用 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
最朴素的递归
# python3: 时间 540 ms, 击败 21.56%; 内存 16 MB, 击败 45.45%
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
return self.fib(n-1) + self.fib(n-2)
// c++: 时间 12 ms, 击败 18.21%; 内存 5.9 MB, 击败 42.21%
class Solution {
public:
int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n-1) + fib(n-2);
}
};
// java: 时间 8 ms, 击败 22.69%; 内存 38.2 MB, 击败 53.50%
class Solution {
public int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n-1) + fib(n-2);
}
}
// go: 时间 12 ms, 击败 16.18%; 内存 1.8 MB, 击败 81.26%
func fib(n int) int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2)
}
// javascript: 时间 84 ms, 击败 15.69%; 内存 40.8 MB, 击败 63.70%
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
if (n <= 1) {
return n;
}
return fib(n-1) + fib(n-2);
};
递归+备忘录
# python3: 时间 48 ms, 击败 39.47%; 内存 16.1 MB, 击败 24.54%
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
self.memo = {0:0, 1:1}
return self.recur(n)
def recur(self, n: int) -> int:
if n in self.memo:
return self.memo[n]
self.memo[n] = self.recur(n-1) + self.recur(n-2)
return self.memo[n]
// c++: 时间 0 ms, 击败 100%; 内存 6.2 MB, 击败 5.11%
class Solution {
public:
int fib(int n) {
if (n <= 1) {
return n;
}
unordered_map<int, int> memo {
{0, 0},
{1, 1}
};
return recur(memo, n);
}
int recur(unordered_map<int, int> & memo, int n) {
unordered_map<int, int>::iterator mit = memo.find(n);
if (mit != memo.end()) {
return mit->second;
}
memo[n] = recur(memo, n-1) + recur(memo, n-2);
return memo[n];
}
};
// java: 时间 0 ms, 击败 100%; 内存 38.3 MB, 击败 24.16%
class Solution {
public int fib(int n) {
if (n <= 1) {
return n;
}
Map<Integer, Integer> memo = new HashMap<>() {{
put(0, 0);
put(1, 1);
}};
return recur(memo, n);
}
private int recur(Map<Integer, Integer> memo, int n) {
if (memo.containsKey(n)) {
return memo.get(n);
}
memo.put(n, recur(memo, n-1) + recur(memo, n-2));
return memo.get(n);
}
}
// go: 时间 0 ms, 击败 100%; 内存 1.8 MB, 击败 52.4%
func fib(n int) int {
if n <= 1 {
return n
}
memo := map[int]int{0:0, 1:1}
return recur(memo, n)
}
func recur(memo map[int]int, n int) int {
if res, ok := memo[n]; ok {
return res
}
memo[n] = recur(memo, n-1) + recur(memo, n-2)
return memo[n]
}
// javascript: 时间 60 ms, 击败 69.18%; 内存 40.8 MB, 击败 40.79%
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
if (n <= 1) {
return n;
}
const memo = new Map([
[0, 0],
[1, 1]
]);
return recur(memo, n);
};
const recur = function(memo, n) {
if (memo.has(n)) {
return memo.get(n);
}
memo.set(n, recur(memo, n-1) + recur(memo, n-2));
return memo.get(n);
}
空间优化为O(N)的自底向上
# python3: 时间 48 ms, 击败 39.47%; 内存 16.1 MB, 击败 5.23%
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
memo = [0] * (n+1)
memo[0] = 0
memo[1] = 1
for i in range(2, n+1):
memo[i] = memo[i-1] + memo[i-2]
return memo[n]
// c++: 时间 4 ms, 击败 38.65%; 内存 6 MB, 击败 6.20%
class Solution {
public:
int fib(int n) {
if (n <= 1) {
return n;
}
int* memo = new int[n+1];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; ++i) {
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}
};
// java: 时间 0 ms, 击败 100%; 内存 38.2 MB, 击败 54.75%
class Solution {
public int fib(int n) {
if (n <= 1) {
return n;
}
int[] memo = new int[n+1];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; ++i) {
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}
}
// go: 时间 0 ms, 击败 100%; 内存 1.8 MB, 击败 37.82%
func fib(n int) int {
if n <= 1 {
return n
}
memo := make([]int, n+1)
memo[0] = 0
memo[1] = 1
for i := 2; i <= n; i++ {
memo[i] = memo[i-1] + memo[i-2]
}
return memo[n]
}
// javascript: 时间 68 ms, 击败 36.78%; 内存 40.8 MB, 击败 42.86%
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
if (n <= 1) {
return n;
}
const memo = new Array(n+1);
memo[0] = 0;
memo[1] = 1;
for (let i = 2; i <= n; ++i) {
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
};
空间优化为O(1)的自底向上
# python3: 时间 44 ms, 击败 54.71%; 内存 15.9 MB, 击败 51.57%
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
prev, curr = 0, 1
for _ in range(2, n+1):
prev, curr = curr, prev + curr
return curr
// c++: 时间 4 ms, 击败 38.65%; 内存 5.9 MB, 击败 31.61%
class Solution {
public:
int fib(int n) {
if (n <= 1) {
return n;
}
int prev = 0, curr = 1;
for (int i = 2; i <= n; ++i) {
int next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
};
// java: 时间 0 ms, 击败 100%; 内存 38 MB, 击败 86.25%
class Solution {
public int fib(int n) {
if (n <= 1) {
return n;
}
int prev = 0, curr = 1;
for (int i = 2; i <= n; ++i) {
int next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
}
// go: 时间 0 ms, 击败 100%; 内存 1.8 MB, 击败 81.26%
func fib(n int) int {
if n <= 1 {
return n
}
prev, curr := 0, 1
for i := 2; i <= n; i++ {
prev, curr = curr, prev + curr
}
return curr
}
// javascript: 时间 60 ms, 击败 69.18%; 内存 40.8 MB, 击败 50.4%
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
if (n <= 1) {
return n;
}
let prev = 0, curr = 1;
for (let i = 2; i <= n; ++i) {
let next = prev + curr;
prev = curr;
curr = next;
}
return curr;
};