斐波那契数 ╰+哭是因爲堅強的太久メ 2022-06-08 02:46 140阅读 0赞 > 牛客网 《剑指offer》 时间限制:`1秒` 空间限制:`32768K` 热度指数:`199742` **解题思路** 一: 如果像这样,将会有大量的计算是重复的,时空复杂度过大 ![这里写图片描述][SouthEast] ![这里写图片描述][SouthEast 1] 二: 可以考虑将计算过的结果缓存起来,如果发现一个 `n` 已经计算过了,就不再重复计算 三: 非递归解法,即从下往上算 首先根据 `f(0)`和 `f(1)` 算出 `f(2)`,再根据`f(1)` 和 `f(2)`算出`f(3)`。。。以此类推 python 2.7 递归 # -*- coding:utf-8 -*- class Solution: def __init__(self): self.dic = { 0:0, 1:1} def Fibonacci(self, n): # write code here if n < 0: return None if self.dic.has_key(n): return self.dic[n] m1 = self.getF(n - 1) if not m1: m1 = self.Fibonacci(n - 1) self.dic[n - 1] = m1 m2 = self.getF(n - 2) if not m2: m2 = self.Fibonacci(n - 2) self.dic[n - 2] = m2 return m1 + m2 def getF(self, n): if self.dic.has_key(n): return self.dic[n] return None 运行时间:28ms 占用内存:5768k > [https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97.py][https_github.com_Jack-Lee-Hiter_AlgorithmsByPython_blob_master_Target_20Offer_E6_96_90_E6_B3_A2_E9_82_A3_E5_A5_91_E6_95_B0_E5_88_97.py] ''' 题目一:大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。 n<=39 题目二:一只青蛙一次可以跳上一级台阶,也可以跳上两级台阶,问该青蛙跳上一个 n 级台阶有多少种跳法? 题目三:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 解法参见牛客网讨论:https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387 ''' # -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): tempArray = [0, 1] if n >= 2: for i in range(2, n+1): tempArray[i%2] = tempArray[0] + tempArray[1] return tempArray[n%2] # 青蛙跳台阶, 每次可以跳1级或2级 def jumpFloor(self, number): # write code here tempArray = [1, 2] if number >= 3: for i in range(3, number + 1): tempArray[(i + 1) % 2] = tempArray[0] + tempArray[1] return tempArray[(number + 1) % 2] def jumpFloorII(self, number): ans = 1 if number >= 2: for i in range(number-1): ans = ans * 2 return ans test = Solution() print(test.Fibonacci(100)) print(test.jumpFloor(3)) print(test.jumpFloorII(2)) [SouthEast]: /images/20220608/391733c7248b4c05a95f7babc5e4d905.png [SouthEast 1]: /images/20220608/15d664439272498f833f9fffc7bbe178.png [https_github.com_Jack-Lee-Hiter_AlgorithmsByPython_blob_master_Target_20Offer_E6_96_90_E6_B3_A2_E9_82_A3_E5_A5_91_E6_95_B0_E5_88_97.py]: https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97.py
还没有评论,来说两句吧...