Leetcode算法基础篇-递归算法

递归算法

递归（Recursion）：指的是一种通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中，可以通过在函数中再次调用函数自身的方式来实现递归。

递归思路

递归过程：问题分解为子问题。
回归过程：子问题回归原问题。

递归算法三步走：

写出递推公式：列举示例、找出原问题到子问题的规律，写出递推公式。
明确终止条件：思考出递归的终止条件和终止时处理方法。
代码实现：将思路翻译为代码。

def recursion(problem):if condition:stop and solvereturn recursion(subproblem)

递归的优化

递归的策略是将问题划分为子问题进行解决，子问题计算过程中，可能出现重叠情况，即重复运算的问题，这时候就需要考虑记忆化递归来解决。

简单的讲，记忆化递归就是我们对于每个子问题，实际上只计算一次，具体做法就是，我们把每次未算过的子问题，计算后记录下答案；下次再计算子问题时，首先看是否有子问题答案，有就直接返回，没有就计算更更新，从而大大简化重复计算量。

def memo_recursion(problem):if condition:stop and solveif subproblem is solved:return ansans = meo_recursion(subproblem)return ans

练习题

509. 斐波那契数

思路

递推公式明确，直接递归。
优化：设置memo字典，记忆化递归。

代码

直接递归：

class Solution:def fib(self, n: int) -> int:if n <= 1:return nreturn self.fib(n - 1) + self.fib(n - 2)

记忆化递归优化：

class Solution:mem = {}def fib(self, n: int) -> int:if n <= 1:return nr1, r2 = 0, 0if n - 1 not in self.mem.keys():self.mem[n - 1] = self.fib(n - 1)r1 = self.mem[n - 1]if n - 2 not in self.mem.keys():self.mem[n - 2] = self.fib(n - 2)r2 = self.mem[n - 2]return r1 + r2

104. 二叉树的最大深度

思路

二叉树当前最大高度:
- 如果根节点空，则高度为0
- 如果没有左子树，则高度为右子树最大高度 + 当前节点（即高度1）
- 如果没有右子树，则高度为左子树最大高度 + 当前节点（即高度1）
- 否则为左右字数的最大高度取大者 + 当前节点（即高度1）
代码实现。

代码

# 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
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0if not root.left:return self.maxDepth(root.right) + 1if not root.right:return self.maxDepth(root.left) + 1return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

0206. 反转链表

思路

考虑子问题：一个两个节点的链表反转过程
- 首节点连接到后面
- 尾节点连接到首节点
- 头指针指向尾节点（新头）
类推，代码实现。

代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head || !head->next) return head;ListNode dummy;while(head) {ListNode *t = head->next;head->next = dummy.next;dummy.next = head;head = t;}return dummy.next;}
};

92. 反转链表 II

思路

反转链表操作已经掌握；
遍历链表，分别找到left和right位置的节点，把链表分为左链表、待反转链表、右链表三个部分；
最后结果即为三个部分连接。

代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head || !head->next) return head;ListNode dummy;while(head) {ListNode* t = head->next;head->next = dummy.next;dummy.next = head;head = t;}return dummy.next;}ListNode* reverseBetween(ListNode* head, int left, int right) {if(left == right) return head;ListNode dummy(0, head);ListNode *p = head;ListNode *pre = &dummy;right -= left; # 区间长度while(p && left > 1) {left--;pre = p;p = p->next;}if(!p) return head; // 只有左链表ListNode *q = p->next;while(q && right > 1) {right--;q = q->next;}if(!q) pre->next = reverseList(p); // 没有右链表ListNode *t = q->next;q->next = nullptr; // 断开待反转链表与右链表pre->next = reverseList(p);p->next = t;return dummy.next;}
};

779. 第K个语法符号

思路

枚举，找规律：每一行的后半部分正好为前半部分的翻转（0变1,1变0），且每一行前半部分和上一行相同。
对于第n行的k列，如果k在后半部分，即求上一行对应k位置的数字的翻转；如果k在前半部分，即求上一行对应k位置的数字。

代码

class Solution {
public:int kthGrammar(int n, int k) {if(n == 1) return 0;if(n == 2) return k - 1;int cnt = 1 << (n - 2); // 上一行数字数量if(k > cnt) {return 1 ^ kthGrammar(n - 1, k - cnt); // 异或操作，翻转01}return kthGrammar(n - 1, k);}
};