X Tutup
Skip to content

recursion.md

Latest commit

 

History

History
164 lines (126 loc) · 4.63 KB

recursion.md

File metadata and controls

164 lines (126 loc) · 4.63 KB

递归

介绍

将大问题转化为小问题，通过递归依次解决各个小问题

示例

reverse-string

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组  char[]  的形式给出。

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        def rev_rec(s, i, j):
            if i >= j:
                return
            s[i], s[j] = s[j], s[i]
            rev_rec(s, i + 1, j - 1)
            return
        
        rev_rec(s, 0, len(s) - 1)
        
        return
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        mid = len(s) // 2
        for i in range(mid):
            s[i], s[-i-1] = s[-i-1], s[i]
        return s

swap-nodes-in-pairs

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        
        if head is not None and head.next is not None:
            head_next_pair = self.swapPairs(head.next.next)
            p = head.next
            head.next = head_next_pair
            p.next = head
            head = p
        
        return head
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head and head.next:
            next_pair = self.swapPairs(head.next.next)
            temp = head.next
            head.next = next_pair
            temp.next = head
            head = temp
        return head

unique-binary-search-trees-ii

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

注意：此题用来训练递归思维有理论意义，但是实际上算法返回的树并不是 deep copy，多个树之间会共享子树。

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        
        def generateTrees_rec(i, j):
            
            if i > j:
                return [None]
            
            result = []
            for m in range(i, j + 1):
                left = generateTrees_rec(i, m - 1)
                right = generateTrees_rec(m + 1, j)
                
                for l in left:
                    for r in right:
                        result.append(TreeNode(m, l, r))
            
            return result
        
        return generateTrees_rec(1, n) if n > 0 else []
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if not n:
            return []
        def helper(i, j):
            if i > j:
                return [None]
            result = []
            for m in range(i, j+1):
                left = helper(i, m-1)
                right = helper(m+1, j)
                for l in left:
                    for r in right:
                        result.append(TreeNode(m, l, r))
            return result
        return helper(1, n)

递归 + 备忘录 (recursion with memorization, top-down DP)

fibonacci-number

斐波那契数，通常用  F(n) 表示，形成的序列称为斐波那契数列。该数列由  0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0,   F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定  N，计算  F(N)。

class Solution:
    def fib(self, N: int) -> int:
        
        mem = [-1] * (N + 2)
        
        mem[0], mem[1] = 0, 1
        
        def fib_rec(n):
            if mem[n] == -1:
                mem[n] = fib_rec(n - 1) + fib_rec(n - 2)
            return mem[n]
        
        return fib_rec(N)
class Solution:
    def fib(self, n: int) -> int:
        if not n:
            return 0
        first, second = 0, 1
        for i in range(2, n+1):
            first, second = second, first + second
        return second

练习
X Tutup