Python算法-递归（Recrusion）

递归-4个要素

• 1 接收的参数
• 2 返回值
• 3 终止的条件
• 4 递归拆解:如何递归到下一层

509:斐波拉契数列
f(n) = f(n-1) + f(n-2)
f(0) =0; f(1) = 1

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:               # 终止条件
            return n 
        return self.fib(n-1) + self.fib(n-2)

206:反转链表
输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL

### 使用递归
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        p = self.reverseList(head.next)
        head.next.next = head       # 两元素链表反向
        head.next = None
        return p

344:反转字符串
输入:['h','e','l','l']
输出:['l','l','e','h']

# 方法1: 双指针
def doublePoint(s):
    left = 0
    right = len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]       # 原地交换
        left += 1       # 左指针右移
        right -= 1      # 右指针左移
    return s
s = ['h','e','l','l']
print(doublePoint(s))

# 方法2:递归+双指针
def reverseList1(s):
    left = 0
    right = len(s) - 1
    if s == None or len(s) == 0:
        return  
    recursion(s, left, right)
    return s

def recursion(s, left, right):
    if left >= right:
        return
    recursion(s, left+1, right-1)
    s[left], s[right] = s[right], s[left]

s = ['h','e','l','l']
# print(reverseList1(s))

二叉树的最大深度

数据结构

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

• 方法1：从上到下计算（前序遍历）-深度优先搜索

1 从根节点开始，每下降一层，就将深度 +1
2 用全局变量来纪录下最大深度
3 每当达到叶子节点时就与全局变量进行比较和更新

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        def dfs(res, root):
            # 叶子节点为空，递归结束
            if root == None:
                return res
            else:
                res += 1
            left_height = dfs(res, root.left)  #
            right_height = dfs(res, root.right)
            return max(left_height, right_height)
        # 初始高度为0
        res = dfs(0, root)
        return res

• 方法2：从下到上计算（后序遍历）深度优先搜索-dfs

思路：已知左子树和右子树的最大深度为 l 和 r, 该二叉树的最大深度为
max_depth = max(l, r) + 1
递归不断分解二叉树

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return self.dfs(root)
    
    def dfs(self, root):
        # 如果是空节点，则深度为 0 
        if root == None:
            return 0
        # 遍历得到左右子树的最大深度
        left_height = self.dfs(root.left)
        right_height = self.dfs(root.right)
        # 返回左右子树的最大深度，再加上根节点的深度
        return max(left_height, right_height) + 1

• 方法3：层序遍历-广度优先搜索

1 使用队列来存放节点
2 一开始先知道当前层数的节点个数，然后根据个数出队，并对其孩子节点入队

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        deque = [root]
        res = 0
        while deque:
            # 层数
            res += 1
            # 找到当前层的节点数
            length = len(deque)
            # 依次取出当前层的节点
            for i in range(length):
                tmpNode = deque.pop(0)
                # 查找左右子树
                if tmpNode.left:
                    deque.append(tmpNode.left)
                if tmpNode.right:
                    deque.append(tmpNode.right)
        return res

62-不同路径

• 动态规划

# class Solution:
#     def uniquePaths(self, m: int, n: int) -> int:
        # dp = [[0 for i in range(n)] for j in range(m)]
        # 第一种写法
        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                # 左边有有效值
                if i-1 >= 0 and i-1 < m:
                    dp[i][j] = dp[i][j] + dp[i-1][j]
                # 右边有有效值
                if j-1 >= 0 and j-1 < n:
                    dp[i][j] = dp[i][j] + dp[i][j-1]
        return dp[m-1][n-1]

        # 第二种写法
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

• 动态规划优化

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [0]*n
        for i in range(n):
            dp[i] = 1
        for i in range(1, m):
            dp[0] = 1
            for j in range(1, n):
                dp[j] = dp[j-1] + dp[j]
                
        return dp[n-1]

• 方法2:递归写法

1 递归关系式:dfs(i,j) = dfs(i-1, j) + dfs(i, j-1)
2 找出初始值:如果i或者j有一个为0,那么不能使用关系式

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        arr = [[0 for i in range(n)] for j in range(m)]
        return self.dfs(m-1, n-1, arr)
    
    def dfs(self, i, j, arr):
        if i == 0 or j == 0:
            return 1
        if arr[i][j] != 0:
            return arr[i][j]
        arr[i][j] = self.dfs(i-1, j, arr) + self.dfs(i, j-1, arr)
        return arr[i][j]

快速幂

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        res = 1
        if n < 0:
            x = 1/x
            n = -n
        while n > 0:
            if n & 1 == 1:
                res *= x
            x *= x
            n = n >> 1
        return res

• 递归算法

        # 递归算法
        if x == 0:
            return 0
        if n < 0:
            x = 1/x
            n = -n
        return self.quitPow(x, n)

    def quitPow(self, x, n):
        if n == 0:
            return 1
        if (n & 1) == 1:
            return x*self.quitPow(x*x, n>>1)
        return self.quitPow(x*x, n>>1)

寻找两个正序数组的中位数

• 排序法

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if nums1 == None and nums2 == None:
            return None

        num = nums1 + nums2
        num.sort()
        length = len(num)
        if length % 2 == 0:
            res = (num[length//2-1] + num[length//2])/2
        else:
            res = num[length//2]
        return res