做网站的去那里接单,常州网站制作方案,织梦网站模板使用教程,自己做的网站点击赚钱文章目录 零 算法介绍一 简单示例 辗转相除法Leetcode例题与思路[509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/)解题思路#xff1a;题解#xff1a; [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)解题思路#xff1a;题解题解 [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)解题思路题解 [面试题 08.06. 汉诺塔问题](https://leetcode.cn/problems/hanota-lcci/)解题思路题解 [94. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/)解题思路题解 [101. 对称二叉树](https://leetcode.cn/problems/symmetric-tree/)解题思路题解 零 算法介绍
递归算法是传统算法中较为简单、基础且实用的一个部分。其核心思想就是通过函数对自身的调用来实现多层嵌套的过程。而在函数递归的时候为了保证程序的正常运行我们需要在程序中设置出口即需要一个判断条件来终止递归。最简单且常用的递归算法就有通过辗转相除法求两个数的最大公因数问题。
一 简单示例 辗转相除法
辗转相除法也被称为欧几里得算法是一种求两个整数的最大公因数GCD的经典算法。这个算法基于一个原理两个整数的最大公因数等于较小数和两数相除余数的最大公因数。
具体步骤如下 将两个数假设为a和b中的大数a除以小数b得到余数r。 将b和余数r作为新的两个数重复步骤1直到余数为0。 余数为0时的除数就是最大公因数。
以下是通过循环求解的思路
# 被除数 将会等于 除数
# 除数 将会等于 余数
# 考虑能否被递归
# 1. 是否存在相同的算法
# 2. 它的终止条件是否唯一
# 考虑到递归的终止条件
# 递归是从最后一层反向传到第一层
def gcd(a, b): while b ! 0: a, b b, a % b return a print(gcd(48, 18))
# 18而当我们采用递归的方式实现时
def gcd(a, b):return gcd(b, a % b) if a % b ! 0 else bprint(gcd(48, 18))
# 18Leetcode例题与思路
接下来我们列举关于Leetcode的五道例题并通过递归的方式进行求解
509. 斐波那契数
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1
给定 n 请计算 F(n) 。
解题思路
关于这道题其实题目中已经给清了思路我们按照公式整理即可详情可看题解。
题解
class Solution:def fib(self, n: int) - int:return self.fib(n-1) self.fib(n-2) if n 1 else n206. 反转链表
给你单链表的头节点 head 请你反转链表并返回反转后的链表。 解题思路
这道题的解题思路其实有很多递归仅是其中一个由于本章是关于递归算法的介绍所以不做其他方面的阐述。
那么我们来说一下递归的解法
首先关于递归算法我们最需要关注的问题是它的终止条件是什么 在这道题里链表的终止条件似乎是循环到head None才算结束了。但是问题仅是这样吗我们需要向下思考一层那就是当我们在最后一个节点的情况下如何指向上一个节点在单链表中显然这是不被允许的所以这道题有很关键的一步是我们判断终止的条件是head.next ≠ None。
当终止条件考虑过后我们就可以考虑递归的主体了。在主程序中由于我们的条件保证head.next ≠ None所以我们可以使得head.next.next head 这样就可以保证当前节点的下一个节点指向自己。而为了保证我们最后可以拿到逆序后的头节点我们只需要返回原来链表中的最后一个元素。
题解
class Solution:def reverseList(self, head: ListNode) - ListNode:if head is None or head.next is None: # 判断边界并返回逆序后的头节点return headrenode self.reverseList(head.next)head.next.next headhead.next Nonereturn renode面试题 08.06. 汉诺塔问题
在经典汉诺塔问题中有 3 根柱子及 N 个不同大小的穿孔圆盘盘子可以滑入任意一根柱子。一开始所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。
请编写程序用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
解题思路
汉诺塔是一道非常经典的递归题目我也非常喜欢。解这道题最好你玩过汉诺塔这样你就会有一个基本的逻辑在。不说其他的了我们来说一下汉诺塔的解题思路关于这道题我做一个很形象的比喻把大象关进冰箱需要几步只需要三步打开冰箱门放进大象关上冰箱门。忽然这么一说你可能摸不到头脑但我们可以这么理解
将汉诺塔从原始柱移到目标柱需要几步只需要三步把前N-1层移动到临时柱把第N层移动到目标柱把前N-1层在移动到目标柱上。
记住这个逻辑后面代码中我将通过raw,temp,aim来替换掉A,B,C。
那这道题目的终止条件是什么呢
当然是仅剩下一层的时候我该怎么移动了。很简单从原始柱移动到目标柱就可以了。
那么由于对于N层来说我们需要把前N-1层移动到临时柱。那么对于前N-1层那个临时柱就变成了它的目标。提示到这里聪明的你应该有想法了那么更精彩的就在代码里了。
题解
class Solution:def hanota(self, A: List[int], B: List[int], C: List[int]) - None:n len(A)raw, temp, aim A, B, Cself.move(n, raw, temp, aim)def move(self, n, raw, temp, aim):if n 1:aim.append(raw[-1])raw.pop()return else:self.move(n-1, raw, aim, temp)aim.append(raw[-1]) raw.pop() self.move(n-1,temp, raw, aim)94. 二叉树的中序遍历
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。
解题思路
如果你不知道二叉树的遍历那么很遗憾你需要先补习相关知识之前说的递归的知识其实已经足够了。二叉树和递归其实是相互纠缠的一对儿所以我们还要讲几到二叉树的题目。
中序遍历即左子树根结点右子树三步走。
而在这道题中我们先找一下终止条件即作为树的叶子节点即可返回。
而在程序主体中我们进需要按照左中右的逻辑对列表做拼接即可。
还需要注意一点就是要小心空树哦。
题解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:if root None:return []elif root.left None and root.right None:return [root.val]else:my_list self.inorderTraversal(root.left) if root.left ! None else []my_list my_list [root.val]my_list my_list self.inorderTraversal(root.right) if root.right ! None else my_listreturn my_list101. 对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。
解题思路
如何判断一个二叉树是否对称它仅满足一个条件即二叉树的左子树和右子树呈现镜像对称。什么意思呢就是左子树的右节点应该风雨右子树的左节点。
去判断一棵树满足对称二叉树的条件不如去找他不满足的地方。这是算法那种的一个很重要的思想判断成功需要挨个证明但判断失败仅需要一次就行。
那接下来我们来说一下终止条件 成功当左右镜像最后都成为None的情况下就是最终的胜利。 迭代当左右都没到叶子节点的时候且左右根的值相同。 失败不满足以上条件就是失败。
所以代码很简单可以写成一下形式
题解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def isSymmetric(self, root: Optional[TreeNode]) - bool:def search(left, right):if left None and right None:return Trueelif left ! None and right ! None and left.val right.val:return search(left.left, right.right) and search(left.right, right.left)else:return Falsereturn search(root.left, root.right) if root ! None else True以上就是关于递归的一些见解我将不定期的更新该系列来完善基于python的算法体系。
