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

leetcode刷题---递归思想

leetcode刷题---递归思想)

  • 1.1 递归介绍
  • 1.2 基本步骤
  • 1.3 代表题目
    • 1.3.1 入门题---青蛙跳
    • 1.3.2.1 初级题
      • 226.翻转二叉树
      • 112.路径总和
    • 1.3.3 中级题---汉诺塔问题
    • 1.3.4 进阶题---细胞分裂

1.1 递归介绍

如果在函数中存在着调用函数本身的情况,这种现象就叫递归。

递归的思想就是,将大问题分解为小问题来求解,然后再将小问题分解为更小的问题。这样一层层地分解,直到问题规模被分解得足够小,不用继续分解,可以直接计算结果为止。

如果把这个一层层分解的过程画成图,它其实就是一颗树,叫做递归树。以斐波那契数列为例子:

    def fib(n):if n <= 1:return 1return fib(n - 1 ) + fib(n - 2)

递归树如下图所示:
在这里插入图片描述
在这里插入图片描述

递归在“归”的过程中,符合后进先出的规则,所以需要用一个堆栈的数据结构。递归过程中函数调用会自动产生栈帧,当函数帧栈的深度越来越大的时候,栈也越来越大,如果递归没有终止条件,就会爆栈。所有基于递归思想实现的算法,第一步要思考的就是递归的终止条件。

进一步剖析「递归」,先有「递」再有「归」,「递」的意思是将问题拆解成子问题来解决, 子问题再拆解成子子问题,…,直到被拆解的子问题无需再拆分成更细的子问题(即可以求解),「归」是说最小的子问题解决了,那么它的上一层子问题也就解决了,上一层的子问题解决了,上上层子问题自然也就解决了。

递归的一般结构

    def func():if (符合边界条件):return# 某种形式的调用func()

1.2 基本步骤

(1) 定义一个函数,明确函数功能

(2) 寻找问题与子问题之间的关系(递推公式)

(3) 将递推公式在定义的函数中实现

(4) 推导时间复杂度,判定是否可以接受,无法接受更换算法

1.3 代表题目

1.3.1 入门题—青蛙跳

一只青蛙可以一次跳 1 级台阶或者一次跳 2 级台阶,例如:
跳上第 1 级台阶只有一种跳法:直接跳 1 级即可。
跳上第 2 级台阶有两种跳法:每次跳 1 级,跳两次;或者一次跳 2 级。
问要跳上第 n 级台阶有多少种跳法?:

一只青蛙只能跳一步或两步台阶,自上而下地思考,也就是说如果要跳到 n 级台阶只能从 从 n-1 或 n-2 级跳 。那么从以上分析可得 f(n) = f(n-1) + f(n-2),显然这就是我们要找的问题与子问题的关系,而显然当 n = 0, n = 1, 即跳一二级台阶是问题的最终解 。

递归解法:

def numWays(n):if n == 0 or n == 1:return 1return numWays(n - 1) + numWays(n - 2)时间复杂度高,因为在递归过程中有大量的重复计算。

优化1:空间换时间

def numWays(n):mid = [0] * (n + 1)if n == 0 or n == 1:return 1mid[0] = mid[1] = 1for i in range(2, n + 1):mid[i] = mid[i - 1] + mid[i - 2]return mid[n]空间换时间,时间复杂度O(n),空间复杂度O(n)

优化2:自下而上的方法

def numWays(n):if n == 0 or n == 1:return 1res = 0pre = 1next = 1for i in range(2, n + 1):res = pre + nextpre = nextnext = resreturn res时间复杂度O(n),空间复杂度O(1)

简单总结一下: 分析问题我们需要采用自上而下的思维,而解决问题有时候采用自下而上的方式能让算法性能得到极大提升,思路比结论重要 。

1.3.2.1 初级题

226.翻转二叉树

在这里插入图片描述
翻转(根节点) = 翻转(根节点的左节点) + 翻转(根节点的右节点) ,即 invert(root) = invert(root->left) + invert(root->right) ,递归的终止条件是当结点为叶子结点时终止(因为叶子节点没有左右结点) 。由于我们会对每一个节点都去做翻转,所以时间复杂度是 O(n), 如果是完全二叉树,空间复杂度为树的高度O(logn) 。最坏情况,如果此二叉树只有左节点,没有右节点,则树的高度即结点的个数 n,此时空间复杂度为 O(n),总的来看,空间复杂度为O(n) 。

def invertTree(self, root):# 叶子节点不能翻转if not root:return root# 翻转右节点下的左右节点right = self.invertTree(root.right)# 翻转左节点下的左右节点left = self.invertTree(root.left)# 左右节点下的二叉树翻转好后,翻转根节点的左右节点root.left = rightroot.right = leftreturn root

112.路径总和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。示例: 
给定如下二叉树,以及目标和 sum = 22,5/ \4   8/   / \11  13  4/  \      \7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

是否存在一条路径,从当前节点root到叶子节点的路径和为sum,这个问题可以转化为:是否存在从当前节点的子节点到叶子的路径和为sum-子节点值。即:

hasPathSum(root,sum)=hasPathSum(root.left,sum-root.val) or hasPathSum(root.right,sum-root.val)

递归终止条件是当前节点是叶子节点,直接判断sum是否等于节点值即可。

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if not root:return Falseif not root.left and not root.right:return targetSum == root.valreturn self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

1.3.3 中级题—汉诺塔问题

在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。你需要原地修改栈。

将n个圆盘经由B移到C上,可以按照以下三个步骤来分析,首先将A上面的n-1个圆盘看成是一个圆盘:

  1. 将A上面的n-1个圆盘经由C移到B
  2. 将A底下最大的圆盘移到C
  3. 再将B上的n-1个圆盘经由A移到C上

move(n from A to C) = move(n-1 from A to B) + move(A to C) + move(n-1 from B to C)

终止条件我们很容易看出,当 A 上面的圆盘只有一个的时候。

# 将 n 个圆盘从 a 经由 b 移动到 c 上
def hanota(A, B, C):n = len(A)move(n, A, B, C)def move(n, A, B, C):if n == 1:C.append(A.pop())return# 将A上面的n-1个圆盘经由C移动到Bmove(n-1, A, C, B)# 将A底下最大的那块移动到CC.append(A.pop())# 将B上的n-1个圆盘经由A移动到Cmove(n - 1, B, A, C)

1.3.4 进阶题—细胞分裂

相关文章:

leetcode刷题---递归思想

leetcode刷题---递归思想&#xff09;1.1 递归介绍1.2 基本步骤1.3 代表题目1.3.1 入门题---青蛙跳1.3.2.1 初级题226.翻转二叉树112.路径总和1.3.3 中级题---汉诺塔问题1.3.4 进阶题---细胞分裂1.1 递归介绍 如果在函数中存在着调用函数本身的情况&#xff0c;这种现象就叫递…...

ThreadLocal 源码级别详解

ThreadLocal简介 稍微翻译一下&#xff1a; ThreadLocal提供线程局部变量。这些变量与正常的变量不同&#xff0c;因为每一个线程在访问ThreadLocal实例的时候&#xff08;通过其get或set方法&#xff09;都有自己的、独立初始化的变量副本。ThreadLocal实例通常是类中的私有静…...

训练营day17

110.平衡二叉树 力扣题目链接 给定一个二叉树&#xff0c;判断它是否是高度平衡的二叉树。 本题中&#xff0c;一棵高度平衡二叉树定义为&#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 返回 true 。 示…...

Nodejs原型链污染

Nodejs与JavaScript和JSON 有一些人在学习JavaScript时会分不清Nodejs和JavaScript之间的区别&#xff0c;如果没有node&#xff0c;那么我们的JavaScript代码则由浏览器中的JavaScript解析器进行解析。几乎所有的浏览器都配备了JavaScript的解析功能&#xff08;最出名的就是…...

【Vue3】element-plus中el-tree的递归处理赋值回显问题

目录一&#xff1a;先获取所有权限tree二&#xff1a;在获取所有该角色能有的权限tree三&#xff1a;递归处理勾选tree节点由于项目是从0-1开始构建的 rbac都需要重新构建对接 所以涉及到了权限管理和菜单管理 一级菜单包含多个二级菜单 若二级不全选&#xff0c;则一级显示 半…...

C语言---宏

专栏&#xff1a;C语言 个人主页&#xff1a;HaiFan. 专栏简介&#xff1a;本专栏主要更新一些C语言的基础知识&#xff0c;也会实现一些小游戏和通讯录&#xff0c;学时管理系统之类的&#xff0c;有兴趣的朋友可以关注一下。 #define预处理预定义符号define#define定义标识符…...

算法导论—路径算法总结

图算法 单源最短路径 Bellman-Ford算法&#xff1a; 顶点为V&#xff0c;边为E的图 对每条边松弛|V|-1次边权可以为负值若存在一个可以从源结点到达的权值为负值的环路&#xff0c;算法返回False时间复杂度&#xff1a;O(VE) 有向无环图单源最短路径 DAG-SHORTEST-PATHS …...

程序环境--翻译+执行

ANSI C标准下&#xff0c;有两种程序环境。 第1种是翻译环境&#xff0c;在这个环境中源代码被转换为可执行的机器指令。 翻译环境包括&#xff1a;预处理&#xff08;预编译&#xff09;编译汇编链接。四个步骤。 第2种是执行/运行环境&#xff0c;它用于实际执行代码。 链接…...

微信小程序内部那些事

微信小程序没有window、document&#xff0c;它更像是一个类似 Node.js 的宿主环境。因此在小程序内部不能使用 document.querySelector 这样的选择器&#xff0c;也不支持 XMLHttpRequest、location、localStorage 等浏览器 API&#xff0c;只能使用小程序自己提供的 API&…...

这是从零在独自开开发,将是副业赚钱最好的平台!

文章目录最重要的事情放前面1.前言2.简单介绍一下3.【独自开】介绍3.1 分层标准化平台架构3.2 集成第三方数字接口3.3 支持各个行业的系统定制开发4.如何在【独自开】赚钱获取收益?4.1 如何称为【独自开】开发者?最重要的事情放前面 通过平台的审核也可以得到相应的奖金&…...

Spring MVC 之获取参数(对象、JSON格式数据、URL地址参数、文件、Cookie)

文章目录1. 获取单个参数2. 获取多个参数3. 获取对象4. 后端参数重命名 RequestParam5. 接收 JSON 格式的数据 RequestBody6. 从 URL 地址中获取参数 PathVariable7. 上传文件 RequestPart8. 获取Cookie (CookieValue)/Session/header8.1 获取 Request 和 Response 对象8.2 获取…...

永磁同步电机中BEMF电阻的作用

一、电路原理图 二、原理分析 如图一我们测的是相电压&#xff0c;从理论上我们知道我们测得相电压是一个马鞍波形&#xff0c;马鞍波形中并没有隐含 转子的位置和速度信息。那么为什么我们还要有这样一个电路呢&#xff1f; 这个问题其实困惑了我好久&#xff1f;直到有一天…...

JAVA练习45-二叉树的层序遍历

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、题目二叉树的层序遍历 …...

超高精度PID调节器的特殊功能(3)——变送输出(转发)功能及其应用

摘要&#xff1a;变送输出是高级PID控制器的一项重要扩展功能&#xff0c;可用于多区控制、串级控制、比值控制和差值控制以及数据采集及记录。为展示变送输出功能的强大作用&#xff0c;本文主要针对超高精度VPC 2021系列PID控制器&#xff0c;介绍了变送输出的具体功能、参数…...

【C++】nullptr C++中的空指针(C++11)

前言 在平时我们写C/C代码时你可能会看到有人使用NULL表示空指针&#xff0c;也有人用nullptr表示空指针&#xff0c;那么你可能会很好奇它们都是空指针吗&#xff1f;为什么空指针有两种写法&#xff1f;下面就带你了解这背后的原理。 我们都知道NULL是C语言中的空指针&#x…...

笔试题-2023-大疆-数字IC设计【纯净题目版】

回到首页:2023 数字IC设计秋招复盘——数十家公司笔试题、面试实录 推荐内容:数字IC设计学习比较实用的资料推荐 题目背景 笔试时间:2022.08.07应聘岗位:数字IC设计笔试平台:赛码题目评价 难易程度:★★★★★知识覆盖:★★★☆☆超纲范围:★★★☆☆值得一刷:★★★…...

Python dict字典方法完全攻略(全)

我们知道&#xff0c;Python 字典的数据类型为 dict&#xff0c;我们可使用 dir(dict) 来查看该类型包含哪些方法&#xff0c;例如&#xff1a; >>> dir(dict) [clear, copy, fromkeys, get, items, keys, pop, popitem, setdefault, update, values] keys()、value…...

用“AI“挑选一件智慧礼物

在久违的烟火气回归之际&#xff0c;充满希望的生活可能就从精心挑选一件新年礼物开始。在罗列礼品清单时&#xff0c;你会想到 “数据”也是其中之一吗&#xff1f;事实上&#xff0c;几乎所有时下最受欢迎的带有“智能”一词的设备&#xff0c;都是由大量高质量的数据创建。我…...

【Spark分布式内存计算框架——Spark Core】4. RDD函数(下) 重分区函数、聚合函数

重分区函数 如何对RDD中分区数目进行调整&#xff08;增加分区或减少分区&#xff09;&#xff0c;在RDD函数中主要有如下三个函数。 1&#xff09;、增加分区函数 函数名称&#xff1a;repartition&#xff0c;此函数使用的谨慎&#xff0c;会产生Shuffle。 2&#xff09;、…...

智能工厂自动化设备如何将数据采集到物联网云平台上

制造业工厂在进行生产管理、数字化转型升级的过程中&#xff0c;大量自动化设备的数据采集上云一直是困扰厂商的难题之一。因设备种类多、工艺复杂、设备老旧无多余通信接口导致数据无法集中、工艺无法实时管控&#xff0c;加上设备服务商的本地支持比较有限&#xff0c;因此设…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

【Android】Android 开发 ADB 常用指令

查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...