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

算法系列--递归

一.如何理解递归

递归对于初学者来说是一个非常抽象的概念,笔者在第一次学习时也是迷迷糊糊的(二叉树遍历),递归的代码看起来非常的简洁,优美,但是如何想出来递归的思路或者为什么能用递归这是初学者很难分析出来的

笔者在学习的过程中通过刷题,也总结出自己的一些经验,总结来说就是要胆大心细,宏观看待问题

其实很多递归的问题如果从宏观的角度去看,其实特别简单,比如二叉树的后序遍历,他无非就是:

  1. 你先给我一个根节点
  2. 访问根节点的左子树
  3. 访问根节点的右子树
  4. 再打印当前节点的值

对于每一个节点的操作都是相同的,如果从宏观的角度看,我们可以把一个复杂的二叉树想象成一个只有三个节点的二叉树
在这里插入图片描述
把二叉树的后序遍历就当做访问这个只有三个节点的二叉树,按照左右根的顺序遍历

dfs(TreeNode root) {if(root == null) return;dfs(root.left);// 访问左节点dfs(root.right);// 访问右结点println(root.val);// 打印当前节点的值
}

大致总结下来递归问题的思路如下:

  1. 分析:根据题目分析,判断是否有重复的子问题,如果有,就可以利用递归解决,设计出函数头,从宏观的角度想,要完成这次操作,这个"接口"需要什么参数(二叉树的遍历需要root,快排需要一个数组和开始结束位置)
  2. 设计函数体:只关注某一个子问题的具体操作,比如二叉树的后序遍历的子问题就完成三步:访问左子树,访问右子树,打印当前节点
  3. 递归出口:确定好递归出口,将子问题分割到最小单元进行确定,比如二叉树的遍历当节点为空时就不需要再去执行任何操作了,直接返回即可,快排,分割到数组只有一个数字或者为空时(l >= r)就不需要继续分治了

二.例题解析:

1.汉诺塔问题

链接:https://leetcode.cn/problems/hanota-lcci/description/

分析:

  1. 函数头:给我三个柱子和盘子数
  2. 函数体:先借助c将a上的n-1个盘子移动到b,然后将a剩余的最大的盘子移动到c,再借助a,将b上的n-1个盘子移动到c
  3. 递归出口:当只有一个盘子的时候,直接移动
    在这里插入图片描述

代码:

class Solution {public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {int n = A.size();dfs(A,B,C,n);}private void dfs(List<Integer> a, List<Integer> b, List<Integer> c,int n) {// 递归结束条件 只有一个盘子的时候直接移动if(n == 1) {c.add(a.remove(a.size() - 1));return;}// 模拟:借助c,将a上的n-1个盘子移动到b上dfs(a,c,b,n-1);// 将最大的盘子移动到c上c.add(a.remove(a.size() - 1));// 模拟:借助a,将b盘上的n-1个盘子移动到c上dfs(b,a,c,n-1);}
}

2.合并两个有序链表

链接: https://leetcode.cn/problems/merge-two-sorted-lists/

分析:

  1. 函数头:两个链表的头结点
  2. 函数体:判断较小值,合并之后的所有节点,并连接返回的节点
  3. 递归出口:只有一个节点或者为空
    在这里插入图片描述

代码:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 递归if(list1 == null) return list2;if(list2 == null) return list1;// 将后面的链表给我合并好,并且返回合并好的节点if(list1.val < list2.val) {list1.next = mergeTwoLists(list1.next,list2);return list1;}else {list2.next = mergeTwoLists(list2.next,list1);return list2;}}
}

3.反转链表

链接: https://leetcode.cn/problems/reverse-linked-list/submissions/514361305/

分析:

  1. 函数头:给我头结点,逆序整个链表
  2. 函数体:逆序之后的所有节点,并且返回逆序之后的头结点,然后和当前节点拼接
  3. 递归出口:只有一个节点或者为空
    在这里插入图片描述

代码:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {// 递归出口if(head == null || head.next == null) return head;// 函数体  你给我逆置后面的所有链表并且返回新的头结点ListNode newhead = reverseList(head.next);// 反转head.next.next = head;head.next = null;return newhead;}
}

4.两两交换链表中的节点

链接: https://leetcode.cn/problems/swap-nodes-in-pairs/

分析:

  1. 函数头:重复子问题就是`给我一个节点,两两交换后面的链表的所有节点
  2. 函数体:关注每一个子问题要干什么,得到交换后的头节点,然后链接这个头结点
  3. 递归出口:空或者只有一个节点
    在这里插入图片描述

代码:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) return head;ListNode ret = head.next;// 最终要返回的节点应该是head.next(是头结点的下一个节点)ListNode newHead = swapPairs(head.next.next);head.next.next = head;head.next = newHead;return ret;}
}

5.Pow(x, n)- 快速幂

链接: https://leetcode.cn/problems/powx-n/submissions/514390268/

分析:

  1. 函数头:结合快速幂的思想,递归函数就是求x ^ n的值
  2. 函数体:每一个子问题的操作,得到 x ^ n / 2的值,再判断返回的结果的值
  3. 递归出口:n == 0

在这里插入图片描述
代码:

class Solution {public double myPow(double x, int n) {// 注意n可能为负数return n < 0 ? 1.0 / pow(x,-n) : pow(x,n);}public double pow(double x,int n) {if(n == 0) return 1.0;double tmp = pow(x,n/2);return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;}
}

相关文章:

算法系列--递归

一.如何理解递归 递归对于初学者来说是一个非常抽象的概念,笔者在第一次学习时也是迷迷糊糊的(二叉树遍历),递归的代码看起来非常的简洁,优美,但是如何想出来递归的思路或者为什么能用递归这是初学者很难分析出来的 笔者在学习的过程中通过刷题,也总结出自己的一些经验,总结来…...

【JS】替换文本为emjio表情

最终效果展示 T1 T2 T3 T4 需求 把评论你好帅啊啊啊[开心][开心]&#xff0c;[开心] 替换为图片 思路 正则match提取[开心]到一个数组数组去重创建img标签img标签转文本. 。例&#xff1a;&#xff08;el.outerHTML&#xff09;&#xff0c;将el元素转文本字符串replaceAll…...

Solr完结版

Solr是基于Apache Lucene构建的用于搜索和分析的开源解决方案。提供可拓展索引、搜索功能、高亮显示和文字解析功能。本质是一个java web项目&#xff0c;内嵌Jetty服务器&#xff0c;安装方便。 请求Solr中的控制器&#xff0c;处理完数据后把结果相应给客户端 正向索引&#…...

外包干了5天,技术退步明显。。。。

说一下自己的情况&#xff0c;本科生&#xff0c;19年通过校招进入广州某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&a…...

Cronos zkEVM 基于 Covalent Network(CQT)数据可用性 API,推动其 Layer2 DeFi 生态更好地发展

在一项旨在显著改善 DeFi 生态的战略举措中&#xff0c;Cronos 与 Covalent Network&#xff08;CQT&#xff09;携手合作&#xff0c;以期待 Cronos zkEVM 的推出。这一整合&#xff0c;预计将进一步降低以太坊生态系统的交易成本、提升交易速度&#xff0c;并带来更好的交易体…...

基于SpringBoot的高校办公室行政事务管理系统

采用技术 基于SpringBoot的高校办公室行政事务管理系统的设计与实现~ 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBootMyBatis 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 页面展示效果 功能清单 教师信息管理 办公室管理 办公物资管…...

Linux系统及操作 (04)

Linux系统及操作 (03) RPM 软件包 网络下载对应软件包光盘镜像文件&#xff0c;具备软件包 Windows 系统软件包的管理 可以指定安装位置安装是集中安装到一个目录Linux 系统 与 Windows 系统相反。 常见的软件包&#xff08;生态&#xff09;类型 电脑入侵99%都是通过软件…...

粒子群算法 - 目标函数最优解计算

粒子群算法概念 粒子群算法 (particle swarm optimization&#xff0c;PSO) 由 Kennedy 和 Eberhart 在 1995 年提出&#xff0c;该算法模拟鸟群觅食的方法进行寻找最优解。基本思想&#xff1a;人们发现&#xff0c;鸟群觅食的方向由两个因素决定。第一个是自己当初飞过离食物…...

关于MySQL数据库的学习3

目录 前言: 1.DQL&#xff08;数据查询语言): 1..1基本查询&#xff1a; 1.2条件查询&#xff1a; 1.3排序查询&#xff1a; 1.3.1使用ORDER BY子句对查询结果进行排序。 1.3.2可以按一个或多个列进行排序&#xff0c;并指定排序方向&#xff08;升序ASC或降序DESC&#…...

笔试题——得物春招实习

开幕式排练 题目描述 导演在组织进行大运会开幕式的排练&#xff0c;其中一个环节是需要参演人员围成一个环形。演出人员站成了一圈&#xff0c;出于美观度的考虑&#xff0c;导演不希望某一个演员身边的其他人比他低太多或者高太多。 现在给出n个参演人员的身高&#xff0c;问…...

动手做简易版俄罗斯方块

导读&#xff1a;让我们了解如何处理形状的旋转、行的消除以及游戏结束条件等控制因素。 目录 准备工作 游戏设计概述 构建游戏窗口 游戏方块设计 游戏板面设计 游戏控制与逻辑 行消除和计分 判断游戏结束 界面美化和增强体验 看看游戏效果 准备工作 在开始编码之前…...

【极简无废话】open3d可视化torch、numpy点云

建议直接看文档&#xff0c;很多都代码老了&#xff0c;注意把代码版本调整到你使用的open3d的版本&#xff1a; https://www.open3d.org/docs/release/tutorial/visualization/visualization.html 请注意open3d应该已经不支持centos了&#xff01; 从其他格式转换成open3d…...

C语言经典算法-6

文章目录 其他经典例题跳转链接31.数字拆解32.得分排行33.选择、插入、气泡排序34.Shell 排序法 - 改良的插入排序35.Shaker 排序法 - 改良的气泡排序 其他经典例题跳转链接 C语言经典算法-1 1.汉若塔 2. 费式数列 3. 巴斯卡三角形 4. 三色棋 5. 老鼠走迷官&#xff08;一&…...

【计算机考研】杭电 vs 浙工大 怎么选?

想求稳上岸的话&#xff0c;其他几所学校也可以考虑&#xff0c;以留在本地工作的角度考虑&#xff0c;这几所学校都能满足你的需求。 如果之后想谋求一份好工作&#xff0c;肯定优先杭电是比较稳的&#xff0c;当然复习的时候也得加把劲。 这个也可以酌情考虑&#xff0c;报…...

激活函数

优秀的激活函数&#xff1a; 非线性&#xff1a;激活函数非线性时&#xff0c;多层神经网络可逼近所有函数 可微性&#xff1a;梯度下降更新参数 单调性&#xff1a;当激活函数是单调的&#xff0c;能保证单层网络的损失函数是凸函数 近似恒等性&#xff1a;当参数初始化为…...

使用Jackson进行 JSON 序列化和反序列化

在Spring应用程序中&#xff0c;您可以通过Maven添加Jackson依赖&#xff0c;并创建一个工具类来封装对象的序列化和反序列化方法。以下是详细步骤&#xff1a; 1. 引入 Jackson 依赖 如果使用 Maven&#xff0c;您可以在 pom.xml 文件中添加以下依赖&#xff1a; <depend…...

Linux/Uinx 系统编程:定时器以及时钟同步

本章讨论了定时器和定时器服务;介绍了硬件定时器的原理和基于Intel x86 的PC中的硬件定时器;讲解了CPU操作和中断处理;描述了Linux中与定时器相关的系统调用、库函数和定时器服务命令;探讨了进程间隔定时器、定时器生成的信号&#xff0c;并通过示例演示了进程间隔定时器。编程…...

(Ubuntu中调用相机花屏)Astra plus深度相机--rgb彩色图像花屏解决方法之一

在调试深度相机的过程中只能能调出深度图像和红外图像 在rviz的image的topic中选择彩色图像的话题不显示图像 1、查看相机的usb序列号 lsusb如上图所示&#xff0c;此相机的USB序列号是2bc5:050f,2bc5:060f 其中050f是显示彩色图像的 在这里可通过拔插相机来确定序列号是哪几…...

iPaaS平台能帮助企业解决什么问题?

随着数字化转型的推进&#xff0c;越来越多的企业开始关注如何提高业务效率和灵活性。iPaaS作为一种新型集成平台&#xff0c;它能够帮助企业解决许多与应用程序和数据集成相关的问题。 它能给企业解决什么问题&#xff1f; 以下是 iPaaS 平台通常能够帮助企业解决的一些问题…...

数学建模(灰色关联度 python代码 案例)

目录 介绍&#xff1a; 模板&#xff1a; 案例&#xff1a;哪些原因影响结婚率 数据标准化&#xff1a; 灰色关联度系数&#xff1a; 完整代码&#xff1a; 结果&#xff1a; 介绍&#xff1a; 灰色关联度是一种多指标综合评价方法&#xff0c;用于分析和评价不同指标之…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...

SQL注入篇-sqlmap的配置和使用

在之前的皮卡丘靶场第五期SQL注入的内容中我们谈到了sqlmap&#xff0c;但是由于很多朋友看不了解命令行格式&#xff0c;所以是纯手动获取数据库信息的 接下来我们就用sqlmap来进行皮卡丘靶场的sql注入学习&#xff0c;链接&#xff1a;https://wwhc.lanzoue.com/ifJY32ybh6vc…...

shell脚本质数判断

shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数&#xff09;shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数&#xff09; 思路&#xff1a; 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...

java+webstock

maven依赖 <dependency><groupId>org.java-websocket</groupId><artifactId>Java-WebSocket</artifactId><version>1.3.5</version></dependency><dependency><groupId>org.apache.tomcat.websocket</groupId&…...

Vue 实例的数据对象详解

Vue 实例的数据对象详解 在 Vue 中,数据对象是响应式系统的核心,也是组件状态的载体。理解数据对象的原理和使用方式是成为 Vue 专家的关键一步。我将从多个维度深入剖析 Vue 实例的数据对象。 一、数据对象的定义方式 1. Options API 中的定义 在 Options API 中,使用 …...