基于python的leetcode算法介绍之递归

文章目录

  • 零 算法介绍
  • 一 简单示例 辗转相除法
  • Leetcode例题与思路
    • [509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/)
      • 解题思路：
      • 题解：
    • [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）的经典算法。这个算法基于一个原理：两个整数的最大公因数等于较小数和两数相除余数的最大公因数。

具体步骤如下：

  1. 将两个数（假设为a和b）中的大数a除以小数b，得到余数r。

  2. 将b和余数r作为新的两个数，重复步骤1，直到余数为0。

  3. 余数为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 b
  
print(gcd(48, 18))
# 18

Leetcode例题与思路

接下来，我们列举关于Leetcode的五道例题，并通过递归的方式进行求解：

509. 斐波那契数

斐波那契数 （通常用 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:
        return self.fib(n-1) + self.fib(n-2) if n > 1 else n

206. 反转链表

给你单链表的头节点 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 head
        renode = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return 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, C
        self.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, val=0, left=None, right=None):
#         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_list
            return my_list

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

解题思路：

如何判断一个二叉树是否对称？它仅满足一个条件，即二叉树的左子树和右子树呈现镜像对称。什么意思呢？就是左子树的右节点应该风雨右子树的左节点。

去判断一棵树满足对称二叉树的条件，不如去找他不满足的地方。这是算法那种的一个很重要的思想：判断成功需要挨个证明，但判断失败仅需要一次就行。

那接下来，我们来说一下终止条件：

  1. 成功：当左右镜像最后都成为None的情况下，就是最终的胜利。

  2. 迭代：当左右都没到叶子节点的时候，且左右根的值相同。

  3. 失败：不满足以上条件就是失败。

所以代码很简单可以写成一下形式：

题解：

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def search(left, right):
            if left == None and right == None:
                return True
            elif left != None and right != None and left.val == right.val:
                return search(left.left, right.right) and search(left.right, right.left)
            else:
                return False
        return search(root.left, root.right) if root != None else True

以上就是关于递归的一些见解，我将不定期的更新该系列，来完善基于python的算法体系。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/258134.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

OpenHarmony开发环境快速搭建(无需命令行)

OpenHarmony开发环境快速搭建(无需命令行)

一. 搭建Windows环境 在嵌入式开发中，很多开发者习惯于使用Windows进行代码的编辑，比如使用Windows的Visual Studio Code进行OpenHarmony代码的开发。但当前阶段，大部分的开发板源码还不支持在Windows环境下进行编译，如Hi3861、H…
阅读更多...
数字助听器如何处理声音？

数字助听器如何处理声音？

数字助听器如何处理声音？ 助听器的作用不仅仅是放大声音。为了创建可改进语音识别的自定义声音配置文件，他们以多种方式处理声音。 麦克风 与人耳一样，数字助听器不直接处理声波。首先是麦克风。它们充当换能器，捕获机械波能并将…
阅读更多...
Verilog 仿真可视化

Verilog 仿真可视化

Verilog 仿真可视化 飞多学堂 飞多学堂 2023-12-11 09:37 Posted on 山东 DigitalJS 是一个基于 JavaScript 实现的开源数字电路模拟器，旨在模拟由硬件设计工具（如 Yosys）合成的电路。由弗罗茨瓦夫大学的Marek Materzok开发，源文…
阅读更多...
手机数码品牌网站建设的作用是什么

手机数码品牌网站建设的作用是什么

手机数码产品几乎已经成为成年人必备的，包括手机、电脑、摄像机、键盘配件等，同时市场中相关企业也非常多，消费者可供选择的商品类型也很多样，而对企业来讲，只有不断提升品牌形象、获客拉新等才能不断提升企业地位&…
阅读更多...
easyexcel常见注解

easyexcel常见注解

easyexcel常见注解 一、依赖 <!--阿里巴巴EasyExcel依赖--><dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>2.2.10</version></dependency>二、常见注解 ExcelProperty 注解中…
阅读更多...
绝地求生什么游戏？

绝地求生什么游戏？

绝地求生是一款由蓝洞公司开发并发行的多人在线生存竞技游戏&#xff0c;也是一款备受玩家热爱和追捧的射击游戏。游戏灵感源自于日本电影《葛洛历亚号》&#xff0c;玩家将扮演一名跳伞降落在荒岛上的幸存者&#xff0c;通过收集资源、与其他玩家进行战斗来生存到最后一名&…
阅读更多...
FastApi-快速入门FastApi框架(1)

FastApi-快速入门FastApi框架(1)

前言 本文是该专栏的第1篇&#xff0c;后面会持续分享FastApi以及项目实战的各种干货知识&#xff0c;值得关注。 FastApi是一个现代、快速&#xff08;高性能&#xff09;的基于Python3.6的web框架&#xff0c;用于构建API。它旨在使API开发更快&#xff0c;更简单&#xff0…
阅读更多...
Polar 这又是一个上传

Polar 这又是一个上传

Polar 这又是一个上传 开局还是一个文件上传界面 有前端后缀检查&#xff0c;这个好绕&#xff0c;抓包改后缀就行 绕过后burp可以直接传一个php上去 getshell 但是无法cat flag&#xff0c;感觉权限不够&#xff0c;需要提权。 查找具有suid权限的命令 1system(find / -use…
阅读更多...
网络协议小记

网络协议小记

一、TCP/IP协议 作为一个小萌新&#xff0c;当然我无法将tcp/ip协议的大部分江山和盘托出&#xff0c;但是其中很多面试可能问到的知识&#xff0c;我觉得有必要总结一下&#xff01; 首先&#xff0c;在学习tcp/ip协议之前&#xff0c;我们必须搞明白什么是tcp/ip协议。 1、…
阅读更多...
第二十一章 ： Spring Boot 集成定时任务（一）

第二十一章 ： Spring Boot 集成定时任务（一）

第二十一章 &#xff1a; Spring Boot 集成定时任务&#xff08;一&#xff09; 前言 本章知识点&#xff1a; 介绍使用Spring Boot内置的Scheduled注解来实现定时任务-单线程和多线程&#xff1b;以及介绍Quartz定时任务调度框架&#xff1a;简单定时调度器&#xff08;Simp…
阅读更多...
SpringIOC之AnnotatedElementKey

SpringIOC之AnnotatedElementKey

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…
阅读更多...
【网络安全】—计算机网络基础

【网络安全】—计算机网络基础

文章目录 网络必备基础物理层数据链路层与交换机网络模型OSI/TCP对等传输虚拟局域网VLAN静态路由与配置网络地址转换NAT访问控制列表ACLIP协议与IP地址分类子网掩码网关子网划分总结 计算机网络是指将地理位置不同的、功能独立的多台计算机通过通信线路连接起来&#xff0c;以功…
阅读更多...
部署智能合约以及 javascript 调用合约函数（Web3项目二实战之三）

部署智能合约以及 javascript 调用合约函数（Web3项目二实战之三）

在上一篇 智能合约是Web3项目的核心要务（Web3项目二实战之二） ，我们已然为项目编写了智能合约，在攥写完智能合约后，该项目将完成了一大部分，剩下无非就是用户界面交互的内容。 然而，在码完了智能合约代码后，起着承前启后关键性的便是，前端界面与智能合约的交互。 智能…
阅读更多...
运行hive的beelin2时候going to print operations logs printed operations logs

运行hive的beelin2时候going to print operations logs printed operations logs

运行hive的beelin2时候going to print operations logs printed operations logs 检查HiveServer2的配置文件hive-site.xml&#xff0c;确保以下属性被正确设置&#xff1a; <property><name>hive.async.log.enabled</name><value>false</value>…
阅读更多...
sql_lab中sql注入之union联合注入

sql_lab中sql注入之union联合注入

1.判断注入类型 gxalabs.com - 该网站正在出售&#xff01; - gxalabs 资源和信息。 没有回显 http://sss-s347glt.gxalabs.com/Pass-02/index.php?id1 and 11 http://sss-s347glt.gxalabs.com/Pass-02/index.php?id1 and 12 and11和and12回显效果一致&#xff0c;则判断…
阅读更多...
Ps：文本的基本操作

Ps：文本的基本操作

在输入文字前&#xff0c;先确定是输入点文本还是段落文本&#xff0c;尽管二者可以相互转换。既可以对文本图层中的所有文本统一设置格式、移动或变换&#xff0c;也可以选择其中的一个或几个字符、一行或一段进行编辑。 新建点文本 使用文字工具在画布上单击并开始输入的文字…
阅读更多...
[toolschain] 头文件有下划线报错不好看，ubuntu下vscode如何设置包含目录路径，以及如何找到安装包的头文件

[toolschain] 头文件有下划线报错不好看，ubuntu下vscode如何设置包含目录路径，以及如何找到安装包的头文件

写在前面 本文是把之前的散落在不同blog中的记录&#xff0c;总结单独合成了一篇文章 vscode 如何配置文件路径 之前使用visual studio 感觉在这一点上 更方便&#xff0c;如果vscode 要配置一下 。 新建&#xff1a;c_cpp_properties.json 或者 ctrl shift p在设置中查找 c…
阅读更多...
深度学习目标检测（2）yolov3设计思想

深度学习目标检测（2）yolov3设计思想

YOLOv3基础 YOLOv3算法基本思想可以分成两部分&#xff1a; 按一定规则在图片上产生一系列的候选区域&#xff0c;然后根据这些候选区域与图片上物体真实框之间的位置关系对候选区域进行标注。跟真实框足够接近的那些候选区域会被标注为正样本&#xff0c;同时将真实框的位置…
阅读更多...
[Win10系统] Win10 任务栏软件图标显示为空白 | 解决方案

[Win10系统] Win10 任务栏软件图标显示为空白 | 解决方案

文章目录 [Win10系统] Win10 任务栏软件图标显示为空白 | 解决方案前言产生错误的原因解决方案方法一&#xff1a;手动操作方法二&#xff1a;自动操作 总结 [Win10系统] Win10 任务栏软件图标显示为空白 | 解决方案 前言 有时候&#xff0c;我们在使用 Windows 10 系统时&…
阅读更多...
栈——OJ题

栈——OJ题

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、最小栈1、题目讲解2、思路讲解3、代码实现 二、栈的压入、弹出序列1、题目讲解2、思路讲解…
阅读更多...
最新文章

Copyright @ 2022~2023