当前位置: 首页 > 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;因此设…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

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

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

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

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

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

构建Docker镜像的Dockerfile文件详解

文章目录 前言Dockerfile 案例docker build1. 基本构建2. 指定 Dockerfile 路径3. 设置构建时变量4. 不使用缓存5. 删除中间容器6. 拉取最新基础镜像7. 静默输出完整示例 docker runDockerFile 入门syntax指定构造器FROM基础镜像RUN命令注释COPY复制ENV设置环境变量EXPOSE暴露端…...