leetcode 509 python 多种解法

LeetCode 509题是求解斐波那契数列的问题，可以使用多种解法来解决。以下是几种常见的Python解法：

解法一：递归
可以使用递归的方式来求解斐波那契数列，代码如下：

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

解法二：动态规划
可以使用动态规划的思想来求解斐波那契数列，代码如下：

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

解法三：优化的动态规划
可以使用滚动数组的方式来优化动态规划的空间复杂度，代码如下：

def fib(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n+1):
        prev, curr = curr, prev + curr
    return curr

以上是LeetCode 509题的三种常见解法。

相关问题

leetcode 114 python

引用\[1\]中给出了一段Java代码，是关于LeetCode 114题的解法。这道题的要求是将二叉树展开为一个单链表。引用\[2\]中提到了这道题可以用递归解法，而不一定要求空间复杂度为O(1)。引用\[3\]中给出了一种解题思路，即将左子树插入到右子树的地方，然后将原来的右子树接到左子树的最右边节点，最后重复这个过程直到新的右子树为null。

根据以上引用内容，可以使用递归的方式来解决LeetCode 114题。具体的Python代码如下：

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        
        self.flatten(root.left)
        self.flatten(root.right)
        
        if root.left:
            temp = root.right
            root.right = root.left
            root.left = None
            
            while root.right:
                root = root.right
            root.right = temp

这段代码首先判断根节点是否为空，如果为空则直接返回。然后递归地对左子树和右子树进行展开。如果根节点的左子树不为空，将右子树保存到临时变量temp中，然后将左子树赋值给右子树，左子树置为空。接着，找到新的右子树的最右边节点，将temp连接到该节点的右侧。

这样，通过递归的方式，就可以将二叉树展开为一个单链表。
#### 引用[.reference_title]
- *1* *2* *3* [【LeetCode 114】二叉树展开为链表（Python）](https://blog.csdn.net/Lucy_R/article/details/107827298)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insert_down1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]

leetcode912 python

LeetCode 912题是关于排序数组的问题。以下是一个用Python解决该问题的示例代码：

class Solution:
    def sortArray(self, nums):
        if len(nums) <= 1:
            return nums
        
        mid = len(nums) // 2
        left_half = nums[:mid]
        right_half = nums[mid:]
        
        left_half = self.sortArray(left_half)
        right_half = self.sortArray(right_half)
        
        return self.merge(left_half, right_half)
    
    def merge(self, left, right):
        merged = []
        i = 0
        j = 0
        
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        
        while i < len(left):
            merged.append(left[i])
            i += 1
        
        while j < len(right):
            merged.append(right[j])
            j += 1
        
        return merged

这个解法使用了归并排序的思想，在每一次递归中将数组一分为二，然后合并两个有序数组。最终得到一个排序好的数组。