当前位置: 首页 > news >正文

基于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 bprint(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 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, 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_listreturn 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 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的算法体系。

相关文章:

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

文章目录 零 算法介绍一 简单示例 辗转相除法Leetcode例题与思路[509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/)解题思路:题解: [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)解题思路:题解&…...

2023年度佳作:AIGC、AGI、GhatGPT、人工智能大语言模型的崛起与挑战

目录 前言 01 《ChatGPT 驱动软件开发》 内容简介 02 《ChatGPT原理与实战》 内容简介 03 《神经网络与深度学习》 04 《AIGC重塑教育》 内容简介 05 《通用人工智能》 目  录 前言 2023年是人工智能大语言模型大爆发的一年,一些概念和英文缩写也在这一…...

Axure的交互以及情形的介绍

一. 交互 1.1 交互概述 通俗来讲就是,谁用了什么方法做了什么事情,主体"谁"对应的就是axure中的元件,"什么方法"对应的就是交互事件,比如单击事件、双击事件,"什么事情"对应的就是交互…...

【MATLAB第84期】基于MATLAB的波形叠加极限学习机SW-ELM代理模型的sobol全局敏感性分析法应用

【MATLAB第84期】基于MATLAB的波形叠加极限学习机SW-ELM代理模型的sobol全局敏感性分析法应用 前言 跟往期sobol区别: 1.sobol计算依赖于验证集样本,无需定义变量上下限。 2.SW-ELM自带激活函数,计算具有phi(x)e^x激…...

米游社区表情包整合网站源码

源码介绍 米游社表情包整合网站源码,来自Github大佬的项目,包含米游兔123枚,米游社 玩家12枚,崩坏 星穹铁道112枚,绝区零218枚,NAP32枚,崩坏RPG62枚,崩坏3-1282枚,原神 …...

easyexcel调用公共导出方法导出数据

easyexcel备忘 Slf4j public class ConditionDownloadUtil {//扫描在xboot 包下所有IService 接口的子类, 每次启动服务后, 重新扫描public final static Class[] classesExtendsIService ClassUtil.scanPackageBySuper("cn.exrick.xboot", IService.class).toArra…...

C语言插入排序算法及代码

一、原理 在待排序的数组里&#xff0c;从数组的第二个数字开始&#xff0c;通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫描&#xff0c;找到相应位置并插入。 二、代码部分 #include<stdio.h> #include<stdlib.h> int ma…...

2023年中国法拍房用户画像和数据分析

法拍房主要平台 法拍房主要平台有3家&#xff0c;分别是阿里、京东和北交互联平台。目前官方认定纳入网络司法拍卖的平台共有7家&#xff0c;其中阿里资产司法拍卖平台的挂拍量最大。 阿里法拍房 阿里法拍房数据显示2017年&#xff0c;全国法拍房9000套&#xff1b;2018年&a…...

Android 清除临时文件,清空缓存

python 代码&#xff1a; import os import shutil import tracebackdef delete_folder(path):if os.path.exists(path):print(f"删除文件夹: {path}")shutil.rmtree(path)print("删除完成")def delete_file(path):if os.path.exists(path):print(f"删…...

Guava限流神器:RateLimiter使用指南

1. 引言 可能有些小伙伴听到“限流”这个词就觉得头大&#xff0c;感觉像是一个既复杂又枯燥的话题。别急&#xff0c;小黑今天就要用轻松易懂的方式&#xff0c;带咱们一探RateLimiter的究竟。 想象一下&#xff0c;当你去超市排队结账时&#xff0c;如果收银台开得越多&…...

【六大排序详解】开篇 :插入排序 与 希尔排序

插入排序 与 希尔排序 六大排序之二 插入排序 与 希尔排序1 排序1.1排序的概念 2 插入排序2.1 插入排序原理2.2 排序步骤2.3 代码实现 3 希尔排序3.1 希尔排序原理3.2 排序步骤3.3 代码实现 4 时间复杂度分析 Thanks♪(&#xff65;ω&#xff65;)&#xff89;下一篇文章见&am…...

凸优化问题求解

这里写目录标题 1. 线性规划基本定理2.单纯形法2.1 转轴运算 3. 内点法3.1 线性规划的内点法 1. 线性规划基本定理 首先我们指出&#xff0c;线性规划均可等价地化成如下标准形式 { min ⁡ c T x , s . t A x b , x ⪰ 0 , \begin{align}\begin{cases}\min~c^Tx,\\\mathrm{s.…...

文件操作入门指南

目录 一、为什么使用文件 二、什么是文件 2.1 程序文件 2.2 数据文件 2.3 文件名 三、文件的打开和关闭 3.1 文件指针 3.2 文件的打开和关闭 四、文件的顺序读写 ​编辑 &#x1f33b;深入理解 “流”&#xff1a; &#x1f342;文件的顺序读写函数介绍&#xff1a; …...

Axure之交互与情节与一些实例

目录 一.交互与情节简介 二.ERP登录页到主页的跳转 三.ERP的菜单跳转到各个页面的跳转 四.省市联动 五.手机下拉加载 今天就到这里了&#xff0c;希望帮到你哦&#xff01;&#xff01;&#xff01; 一.交互与情节简介 "交互"通常指的是人与人、人与计算机或物体…...

【数据库设计和SQL基础语法】--连接与联接--多表查询与子查询基础(二)

一、子查询基础 1.1 子查询概述 子查询是指在一个查询语句内部嵌套另一个查询语句的过程。子查询可以嵌套在 SELECT、FROM、WHERE 或 HAVING 子句中&#xff0c;用于从数据库中检索数据或执行其他操作。子查询通常返回一个结果集&#xff0c;该结果集可以被包含它的主查询使用…...

Android studio中导入opencv库

具体opencv库的导入流程参考链接&#xff1a;Android Studio开发之路 &#xff08;五&#xff09;导入OpenCV以及报错解决 一、出现的错误&#xff1a;NullPointerException: Cannot invoke “java.io.File.toPath()” because “this.mySdkLocation” is null 解决办法&#…...

Linux(1)_基础知识

第一部分 一、Linux系统概述 创始人&#xff1a;芬兰大学大一的学生写的Linux内核&#xff0c;李纳斯托瓦兹。 Linux时unix的类系统&#xff1b; 特点&#xff1a;多用户 多线程的操作系统&#xff1b; 开源操作系统&#xff1b; 开源项目&#xff1a;操作系统&#xff0c;应用…...

网络相关面试题

简述 TCP 连接的过程&#xff08;淘系&#xff09; 参考答案&#xff1a; TCP 协议通过三次握手建立可靠的点对点连接&#xff0c;具体过程是&#xff1a; 首先服务器进入监听状态&#xff0c;然后即可处理连接 第一次握手&#xff1a;建立连接时&#xff0c;客户端发送 syn 包…...

Vue2面试题:说一下对跨域的理解?

http请求分为两大类&#xff1a;普通http请求&#xff08;如百度请求&#xff09;和ajax请求&#xff08;跨域是出现在ajax请求&#xff09; 同源策略&#xff1a;在浏览器发起ajax请求时&#xff0c;当前的网址和被请求的网址协议、域名、端口号必须完全一致&#xff0c;目的是…...

Axure中如何使用交互样式交互事件交互动作情形

&#x1f3ac; 艳艳耶✌️&#xff1a;个人主页 &#x1f525; 个人专栏 &#xff1a;《产品经理如何画泳道图&流程图》 ⛺️ 越努力 &#xff0c;越幸运 目录 一、Axure中交互样式 1、什么是交互样式&#xff1f; 2、交互样式的作用&#xff1f; 3、Axure中如何…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...