Python - 深夜数据结构与算法之 Recursion

2023-12-26 09:12
文章标签 python 算法 数据结构 recursion 深夜

本文主要是介绍Python - 深夜数据结构与算法之 Recursion，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一.引言

二.递归的简介

1.Recursion 递归

2.Factorial 阶乘

3.Template 模版

三.经典算法实战

1.Generate-Parentheses [22]

2.Climbing-Stairs [70]

3.Is-Valid-BST [98]

4.Max-Depth [104]

5.Construct-Binary-Tree [105]

6.Min-Depth [111]

7.Invert-Tree [226]

8.Ser-And-Deset-Binary-Tree [297]

9.Low-Common-Ancestor [236]

四.总结

一.引言

前面介绍了树和图，其中很多都用到了递归的方式，本文我们介绍泛型递归以及树的递归，加深对二者的印象。

二.递归的简介

1.Recursion 递归

递归的基本含义是我们通过构建一个函数体，不断自身调用直到停止，其本质上也是循环的一种，用我们小时候的说法叫：

注意虽然递归是循环且不断调用，但是一定要有退出条件，这里使用抽象的返回 1，视实际情况而定。

2.Factorial 阶乘

以阶乘计算为例，递归的实现其实是系统在内部构建一个栈，先进后出，最后一步一步调用出来，这里给出递归树的形式我们称为人肉递归，即自己模拟整个递归过程，用来更直观的理解递归。

3.Template 模版

◆ terminator - 终止条件，避免死循环，调用递归时一定要想好停止或者退出的边界条件

◆ process - 处理逻辑，每层递归的处理逻辑

◆ drill donw - 向下钻，很形象，其实就是到更深的一层继续探索，n -> n+1

◆ reverse state - 一些情况下需要保持该层的状态，此时需要再递归结束后进行恢复

Tips:

学过数学归纳法的同学应该比较熟悉递归，数学归纳法的步骤我们先初始化 f(1)、f(2)，然后推广到 f(n)，最后再证明 f(n+1) 也 ok 就 ok 了，递归也相似，我们需要把可拆解的重复问题进行归纳，然后推广到 f(x) 的通式上。 

三.经典算法实战

1.Generate-Parentheses [22]

括号生成: https://leetcode-cn.com/problems/generate-parentheses/

◆ 题目分析 

首先可以使用暴力法，共 2n 个字符，每次只能出 '(' 或者 ')'，把所有结果的括号验证一下是否可用，即可。还有一种可以递归，观察上面的 n=3 的情况，对于有效的括号而言，其一定满足num-左括号 = num-右括号 and 最左边一定是 '('，所以我们可以从 0 -> n 递归生成并判断合法性。

◆ 逐步生成

class Solution(object):def generateParenthesis(self, n):""":type n: int:rtype: List[str]"""# 保存结果result = []self.generate(0, 0, n, "", result)return resultdef generate(self, left, right, n, s, result):if left == n and right == n:result.append(s)# 保证最左边一定是 '('if left < n:self.generate(left + 1, right, n, s + "(", result)# right 不够就补充if right < left:self.generate(left, right + 1, n, s + ")", result)

从左括号开始，后面遍历全部情况，并通过边界条件对生成进行过滤，避免无效的生成。这里主要还是明确递归四要素:

terminator - len(left) = len(right) && s.start_with('(')

process - s + '('  || s + ')'

drill donw - left + 1 || right + 1

recerse state - 没有全局变量改动，所以无需操作

2.Climbing-Stairs [70]

爬楼梯问题: https://leetcode-cn.com/problems/climbing-stairs/

◆ 题目分析 

我们尝试使用数学归纳法的思想，因为一次只能走 1 or 2 步，所以 f(1) = 1、f(2) = 2、往后类推，对于 f(n) 的情况，其有两种方式到达，一种是 f(n-1) 走 1 步，还有事 f(n-2) 走两步，所以:

f(n) = f(n-1) + f(n-2)

即走到 n 有几种方法，就等于走到 n-1 和 n-2 方法的和，同理，走到 n-1 是走到 n-2 和 n-3 的方法的和，依次类推。退出条件，退出条件就是到达 1 or 2 即可。

◆ 递归实现

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""# 终止条件if n <= 2:return n# 下一层return self.climbStairs(n-1) + self.climbStairs(n-2)

这里我们根据递归的模版，直接套即可得到上述代码，边界条件的 1->1、2->2 我们合在一起。不过时间超出限制了，我们每次扩展 n-1、n-2 两个分叉，共 n 次，所以时间复杂度是 2^^n，还是有点高，但是能够匹配模版就说明我们递归的思想逐渐熟悉。

◆ 滑动数组

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n <= 2:return na, b, c = 1, 2, 3# 滑动数组for i in range(3, n):a, b, c = b, c, b+creturn c

熟悉 Fib 即斐波那契数列的同学可以看出 f(n) = f(n-1) + f(n-2) 其实是其对应通式，我们可以通过滑动数组的方式，不断向前推进求解，只需要 o(n) 的时间复杂的和常数的空间复杂度。 

3.Is-Valid-BST [98]

有效二叉搜索树: https://leetcode-cn.com/problems/validate-binary-search-tree

◆ 题目分析

二叉搜索树有效的定义在图中已经给出，左边的比 root 小，右边的比 root 大，根据中序遍历 '左根右' 遍历二叉搜索树即可得到一个有序的数组，我们只需判断 pre 节点的值是否小于当前的值即可。

◆ 中序遍历 - 递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution(object):pre = -999999999999999def isValidBST(self, root):# 停止条件if root is None:return True# 遍历左子树if not self.isValidBST(root.left):return False# 上一个值大于等于下一个则为异常if root.val <= self.pre:return Falseself.pre = root.val# 遍历右子树return self.isValidBST(root.right)

参考递归的中序遍历写法，在 val 值处进行递增顺序的判断。

◆ 中序遍历 - 栈

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def isValidBST(self, root):""":type root: TreeNode:rtype: bool"""stack = []cur = rootpre = Nonewhile cur or stack:if cur:stack.append(cur)cur = cur.leftelse:cur = stack.pop()# 在中序遍历的基础上添加了顺序的判断if pre and cur.val <= pre.val:return Falsepre = curcur = cur.rightreturn True

中序遍历的模版，只是在 process val 的位置由 append or print 变成了比较是否有序。

4.Max-Depth [104]

二叉树最大深度: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

◆ 题目分析

采用 DFS 递归遍历左右子树，每 DFS 一层就为层数增加1，最后统计 max(左，右) 即可得到最深的深度。

◆ 递归实现

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""# 停止条件if not root:return 0 else:# 向下出发left_h = self.maxDepth(root.left)right_h = self.maxDepth(root.right)# +1: 根节点return max(left_h, right_h) + 1

 向下遍历，遍历时返回自己位置左右子树较高的层数并加上自己所在层的 1。

5.Construct-Binary-Tree [105]

重建二叉树: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal

◆ 题目分析

pre -> 根左右 in -> 左根右，根据这个逻辑，我们可以从 preorder 确定全局的 root 节点，根据 root 节点的位置，我们在中序遍历中可以获取其左子树和右子树的长度，对于左右子树而言，其前序和中序遍历的长度是一样的，所以可以向下递归，对左右子树分别寻找 root。

◆ 递归遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def buildTree(self, preorder, inorder):""":type preorder: List[int]:type inorder: List[int]:rtype: TreeNode"""# 根据 pre 可以获得根节点if not preorder and not inorder:return None# pre -> 根左右 in -> 左根右root = TreeNode(preorder[0])# 获取根节点位置mid_index = inorder.index(root.val)root.left = self.buildTree(preorder[1: mid_index + 1], inorder[: mid_index])root.right = self.buildTree(preorder[mid_index + 1:], inorder[mid_index + 1:])return root

大家可以结合上面的思路和 GIF 图理解递归的意图。 

6.Min-Depth [111]

二叉树最小深度: https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

◆ 题目分析

采用 DFS 递归遍历左右子树，每 DFS 一层就为层数增加1，最后统计 min(左，右) 即可得到最小的深度，和上面 Max Depth 是反着来的。但是这里求最小路径时，需要注意边际条件 max depth 有一点差别，当一边为空，一边有叶子节点时，min 的判断方法需要修改，参考下图，左边深度 0，右边深度 4，如果采用 min(0, 4) + 1 则最小为 1，但是题目要求根节点到最近的叶节点，所以我们要 if 把一边 root == None 的情况排除掉。

◆ 递归实现

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""# 无根 -> 0if not root:return 0# 无孩 -> 1if not root.left and not root.right:return 1# 向下递归left_height = self.minDepth(root.left)right_height = self.minDepth(root.right)# 当一边为空一边不为空时，min(h,r) 会返回1，但此时 root 存在叶节点，所以 l+r+1# 因为如果有一个为空 其返回为0，不会影响最终结果if not root.left or not root.right:return left_height + right_height + 1return min(right_height, left_height) + 1

按照题解思路实现即可。 

7.Invert-Tree [226]

反转二叉树: https://leetcode-cn.com/problems/invert-binary-tree/description/ 

◆ 题目分析

交换左右子树，对于 root 交换其左右，继续向下对 left 交换左右，对 right 交换左右 ... 典型的递归题目。

◆ 左右递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def invertTree(self, root):""":type root: TreeNode:rtype: TreeNode"""# 停止条件if not root:return None# 处理 左右交换root.left, root.right = root.right, root.left# 向下出发self.invertTree(root.left)self.invertTree(root.right)# 无全局变量修改return root

再啰嗦一遍递归四步法: 停止条件 + 处理 + 下一层 + 恢复状态。

8.Ser-And-Deset-Binary-Tree [297]

BT 序列化与反序列化: https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/ 

◆ 题目分析

这个题目整体来说不麻烦，但是很绕，而且很容易和官方要求的返回内容不一致。我们编码阶段可以通过 BFS 层序遍历将结果生成为符号分割的字符串，或者存到 [] 再使用 ','.jion。解码时只需要根据节点对应关系依次还原 Node 即可，需要注意 python 中如果节点为 None，需要返回特定的字符串标识并在解码时识别，下面示例采用 "null"。

◆ BFS 层序遍历

class Codec:def serialize(self, root):"""Encodes a tree to a single string.:type root: TreeNode:rtype: str"""if not root:return ""queue = collections.deque([root])res = []while queue:node = queue.popleft()if node:res.append(str(node.val))queue.append(node.left)queue.append(node.right)else:res.append('None')return '[' + ','.join(res) + ']'def deserialize(self, data):"""Decodes your encoded data to tree.:type data: str:rtype: TreeNode"""if not data:return []dataList = data[1:-1].split(',')root = TreeNode(int(dataList[0]))queue = collections.deque([root])i = 1while queue:node = queue.popleft()if dataList[i] != 'None':node.left = TreeNode(int(dataList[i]))queue.append(node.left)i += 1if dataList[i] != 'None':node.right = TreeNode(int(dataList[i]))queue.append(node.right)i += 1return root

这里使用 index += 1 和 queue 配合分别决定下一个 node 该匹配给谁。这里博主自己实现了一版通过父亲索引寻找对应节点的方法，本地可以验证但乐扣总是少 None，也懒得纠结了，放在这里有兴趣的同学可以看看，主要思想是通过 parent = int((i - 1) / 2) 的父亲节点计算公式和 choose = ["l", "r"] 决定当前节点该放左还是右。

class Codec:def bfs(self, root):result = []if root is None:returnmy_queue = [root]while my_queue:# 返回列表第一个节点的数据node = my_queue.pop(0)result.append(node.val)if node.left is not None:my_queue.append(node.left)if node.right is not None:my_queue.append(node.right)return resultdef serialize(self, root):"""Encodes a tree to a single string.:type root: TreeNode:rtype: str"""result = []if not root:return ""queue = [root]# BFS 遍历二叉树while queue:node = queue.pop(0)result.append(str(node.val))if node.left:queue.append(node.left)if node.right:queue.append(node.right)return ",".join(result)def deserialize(self, data):"""Decodes your encoded data to tree.:type data: str:rtype: TreeNode"""if not data:returntree = data.split(",")root = TreeNode(int(tree[0]))result = [root]choose = ["l", "r"]for i in range(1, len(tree)):parent = int((i - 1) / 2)c = choose[(i-1) % 2]if tree[i] != "None":cur_tree = TreeNode(int(tree[i]))else:cur_tree = TreeNode(None)if c == "l":result[parent].left = cur_treeresult.append(cur_tree)if c == "r":result[parent].right = cur_treeresult.append(cur_tree)return result[0]

9.Low-Common-Ancestor [236]

二叉树最近公共祖先: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree

◆ 题目分析

根据题目要求，p、q 公共祖先共有如上三种情况，考虑通过递归对二叉树进行前序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p,q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。

◆ DFS 遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""# 退出条件: 顶节点没有祖先了，最高就这么高了if root == None or root == p or root == q:return root# 分别到左右子树找 p、q 的 rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)# 左边没找到，右边找if not left:return right# 右边没找到，左边找if not right:return leftreturn root

此题比较绕，推荐大家看大佬的图文题解: DFS 清晰图解。 

◆ 分头寻找

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""record = {root: None}stack = [root]while stack:node = stack.pop()if node.left:record[node.left] = nodestack.append(node.left)if node.right:record[node.right] = nodestack.append(node.right)# p、q 都找都就可以退出了if p in record and q in record:break# 把 p 的父亲节点都标记while p:parent = record[p]record[p] = Truep = parent# 从 q 向上找，第一个为 True 的即为公共祖先while record[q] is not True:q = record[q]return q

 先通过遍历子树并记录的方法将 p 和 q 的全部父亲节点记录下来，随后标记 p 或者 q 的节点父亲为 True，然后从另一个节点的父亲自下而上寻找，第一个为 True 的就是公共的了。

四.总结

上面介绍了递归以及大量树的题目，因为树的结构与遍历天生比较适合递归实现，上面的题思路都很巧妙，属于看了忘、忘了看、几天不看全忘的状态，还是要多多练习多多巩固。

这篇关于Python - 深夜数据结构与算法之 Recursion的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/538838。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
python: 多模块(.py)中全局变量的导入

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别： 当你在一个模块（文件）中使用 global 声明变量时，这个变量只在该模块的全局命名空
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【Python编程】Linux创建虚拟环境并配置与notebook相连接

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如，在当前目录下创建一个名为 myenv 的虚拟环境： python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行： source myenv/bin/activate 3.与notebook连接 在虚拟环境中，使用 pip 安装 Jupyter 和 ipykernel： pip instal
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程（Gaussian Process，简称GP）是一种概率模型，用于描述一组随机变量的联合概率分布，其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数（或核函数） 1.3 核函数1.4 高斯过程回归（Gauss
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2