首页 > 其他分享 >Leedcode-斐波那契数

Leedcode-斐波那契数

时间:2024-05-23 12:41:03浏览次数:22  
标签:契数 return 数列 self Leedcode 斐波 Fibonacci fib memo

自己写的,递归

class Solution:
    def fib(self, n: int) -> int:
        # 如果 n 是 0,则返回 0,因为这是 Fibonacci 数列的定义
        if n == 0:
            return 0
        # 如果 n 是 1,则返回 1,因为这是 Fibonacci 数列的定义
        elif n == 1:
            return 1
        # 对于其他情况,递归地调用 fib 函数,计算 Fibonacci 数列的前两个数并相加
        else:
            return self.fib(n - 2) + self.fib(n - 1)

 gpt优化,采用记忆优化:

class Solution:
    def __init__(self):
        # 初始化一个字典来存储已经计算过的 Fibonacci 数列值
        self.memo = {}

    def fib(self, n: int) -> int:
        # 如果 n 已经在 memo 中,直接返回其值
        if n in self.memo:
            return self.memo[n]

        # 基本情况:如果 n 是 0 或 1,直接返回 n
        if n == 0:
            return 0
        elif n == 1:
            return 1

        # 递归计算 Fibonacci 数列值,并存储在 memo 中
        self.memo[n] = self.fib(n - 2) + self.fib(n - 1)
        return self.memo[n]

 

标签:契数,return,数列,self,Leedcode,斐波,Fibonacci,fib,memo
From: https://www.cnblogs.com/yyyjw/p/18208163

相关文章

  • Leedcode-完美数
    自己写的:classSolution:defcheckPerfectNumber(self,num:int)->bool:#如果数字是1,则直接返回False,因为1不是完美数ifnum==1:returnFalse#初始化一个空的列表来存储因子factors=[]......
  • Leedcode-相对名次
    自己写的:fromtypingimportListclassSolution:deffindRelativeRanks(self,score:List[int])->List[str]:#获取成绩列表的长度n=len(score)#复制原始成绩列表score_former=score#对成绩列......
  • Leedcode-二叉搜索树中的众数
    自己写的:classSolution:#findMode方法接受一个二叉树的根节点root,并返回一个列表,其中包含树中出现次数最多的值deffindMode(self,root:Optional[TreeNode])->List[int]:#初始化一个队列,用于层次遍历二叉树queue=[root]#初始化......
  • Leedcode-键盘行
    自己写的:classSolution:#定义findWords方法,该方法接受一个字符串列表words作为参数deffindWords(self,words:List[str])->List[str]:#定义三个字符串,分别包含键盘上三行的字母str1="qwertyuiopQWERTYUIOP"#第一行字母str2=......
  • Leedcode-下一个更大元素 I
    自己写的:classSolution:defnextGreaterElement(self,nums1:List[int],nums2:List[int])->List[int]:res=[]#结果列表,用于存储每个nums1中元素在nums2中的下一个更大元素num1_ptr=0#指向nums1当前元素的指针num2_ptr=0#......
  • Leedcode-提莫攻击
    自己写的,中间算法有遗漏的遍历classSolution:deffindPoisonedDuration(self,timeSeries:List[int],duration:int)->int:ifduration==0:#如果duration为0,则返回0,因为没有中毒时间return0count=0#初始化中毒总时间......
  • python: 递归函数:斐波那契数列
    一,认识递归函数1,什么是递归?递归的工作原理是,如果函数需要处理的问题大小合适,则直接求解并返回结果,否则将问题分解成两个或多个更小的子问题,并对子问题进行相同的处理,直到问题无法分解为止2,什么是递归函数:递归函数(recursivefunction)是指在函数体中可以调用自己的函数3,语......
  • Leedcode-构造矩形
    自己写的classSolution:defconstructRectangle(self,area:int)->List[int]:#计算给定面积的平方根root=area**0.5#初始化结果列表,默认为[1,area],即长为面积,宽为1的情况temp=[1,area]#如果面积是一个完全......
  • Leedcode-最大连续 1 的个数
    自己写的:fromtypingimportListclassSolution:deffindMaxConsecutiveOnes(self,nums:List[int])->int:#初始化最大连续1的计数器和临时连续1的计数器count=0temp=0#获取列表长度n=len(nums)#初......
  • Leedcode-密钥格式化
    自己写的:classSolution:deflicenseKeyFormatting(self,s:str,k:int)->str:#将字符串转换为列表,方便操作new_S=list()#遍历输入字符串foriins:#如果当前字符不是'-',则添加到新列表中ifi!......