Leetcode算法基础篇-递归算法
递归算法
递归（Recursion）：指的是一种通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中，可以通过在函数中再次调用函数自身的方式来实现递归。
递归思路
- 递归过程：问题分解为子问题。
- 回归过程：子问题回归原问题。
递归算法三步走：
- 写出递推公式：列举示例、找出原问题到子问题的规律，写出递推公式。
- 明确终止条件：思考出递归的终止条件和终止时处理方法。
- 代码实现：将思路翻译为代码。
def recursion(problem):
if condition:
stop and solve
return recursion(subproblem)
递归的优化
递归的策略是将问题划分为子问题进行解决，子问题计算过程中，可能出现重叠情况，即重复运算的问题，这时候就需要考虑记忆化递归来解决。
简单的讲，记忆化递归就是我们对于每个子问题，实际上只计算一次，具体做法就是，我们把每次未算过的子问题，计算后记录下答案；下次再计算子问题时，首先看是否有子问题答案，有就直接返回，没有就计算更更新，从而大大简化重复计算量。
def memo_recursion(problem):
if condition:
stop and solve
if subproblem is solved:
return ans
ans = meo_recursion(subproblem)
return ans
练习题
509. 斐波那契数
思路
- 递推公式明确，直接递归。
- 优化：设置memo字典，记忆化递归。
代码
直接递归：
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
return self.fib(n - 1) + self.fib(n - 2)
记忆化递归优化：
class Solution:
mem = {}
def fib(self, n: int) -> int:
if n <= 1:
return n
r1, r2 = 0, 0
if 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 0
if not root.left:
return self.maxDepth(root.right) + 1
if not root.right:
return self.maxDepth(root.left) + 1
return 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);
}
};