本文主要是介绍4.每日LeetCode-数组类,斐波那契数(Go,Java,Python),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
题号: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: 输入:n = 2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1示例 2: 输入:n = 3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2示例 3: 输入:n = 4 输出:3 解释:F(4) = F(3) + F(2) = 2 + 1 = 3例如:0 1 1 2 3 5 8 13 21 斐波那契数列0 1 2 3 4 5 6 7 8 下标
解法
Go
package mainimport "fmt"// 使用递归,并用map保存已经求解过的值
func fib1(n int) int {mp := make(map[int]int, n-2)if n <= 1 {return n}if _, ok := mp[n]; ok {return mp[n]} else {rst := fib(n-1) + fib(n-2)mp[n] = rstreturn rst}
}// 使用for循环,用两个变量记录上次和上上次的值,时间复杂度O(n)
func fib(n int) int {if n <= 1 {return n}rst := 0pre := 1prepre := 0for i := 2; i <= n; i++ {rst = pre + prepreprepre = prepre = rst}return rst
}func main() {fmt.Println(fib(7))
}
Java
package org.example;import java.util.HashMap;
import java.util.Map;public class Fibonacci {// 使用递归,并用map保存已经求解过的值private Map<Integer, Integer> mp = new HashMap<>();public int fib1(int n) {if (n == 0) return 0;if (n == 1) return 1;if (mp.get(n) != null) {return mp.get(n);} else {int val = fib1(n - 1) + fib1(n - 2);mp.put(n, val);return val;}}// 使用for循环,用两个变量记录上次和上上次的值,时间复杂度O(n)public int fib(int n) {if (n == 0) return 0;if (n == 1) return 1;int sum = 0, pre = 1, prepre = 0;for (int i = 2; i <= n; i++) {sum = pre + prepre;prepre = pre;pre = sum;}return sum;}}
Python
dic = {}def fib(n):if n == 0:return 0if n == 1:return 1if n in dic:return dic[n]else:val = fib(n - 1) + fib(n - 2)dic[n] = valreturn val# 使用for循环,用两个变量记录上次和上上次的值,时间复杂度O(n)
def fib1(n):if n == 0:return 0if n == 1:return 1sum = 0pre = 1prepre = 0for i in range(2, n + 1):sum = pre + prepreprepre = prepre = sumreturn sumif __name__ == '__main__':print(fib(7))print(fib1(7))
这篇关于4.每日LeetCode-数组类,斐波那契数(Go,Java,Python)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!