算法沉淀——递归(leetcode真题剖析)

在这里插入图片描述

算法沉淀——递归

  • 01.汉诺塔问题
  • 02.合并两个有序链表
  • 03.反转链表
  • 04.两两交换链表中的节点
  • 05.Pow(x, n)

递归是一种通过调用自身的方式来解决问题的算法。在递归算法中,问题被分解为更小的相似子问题,然后通过对这些子问题的解进行组合来解决原始问题。递归算法通常包含两个主要部分:

  1. 基本情况(Base Case): 定义问题的最小规模,直接解答而不再进行递归。基本情况是递归算法的出口,防止算法陷入无限递归。
  2. 递归步骤: 在问题规模较大时,将问题划分为相似但规模较小的子问题,并通过递归调用解决这些子问题。递归调用自身是递归算法的核心。

递归算法在解决许多问题上非常强大,尤其是对于那些可以通过分解为子问题并且存在重叠子问题的情况。递归通常使算法更加简洁、清晰,但需要谨慎处理基本情况,以避免无限递归。

经典的递归问题包括汉诺塔问题、阶乘计算、斐波那契数列等。递归也在许多算法和数据结构中发挥着重要的作用,例如树的遍历、图的深度优先搜索等。

如何理解递归?

1.递归展开的细节图
2.二叉树中的题目
3.宏观看待递归的过程

1.不要在意递归的细节展开图
2.把递归的函数当成一个黑盒
3.相信这个黑盒一定能完成这个任务

如何写好递归?

1.先找到相同的子问题!!!->函数头的设计
2.只关心某一个子问题是如何解决的 ->函数体的书写
3.注意一下递归函数的出口即可

01.汉诺塔问题

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

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

请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例1:

 输入:A = [2, 1, 0], B = [], C = []输出:C = [2, 1, 0]

示例2:

 输入:A = [1, 0], B = [], C = []输出:C = [1, 0]

提示:

  1. A中盘子的数目不大于14个。

思路

对于这类问题我们可以使用数学中的归结思想,先画图分析由1到n的情况,我们可以总结出下面这三个步骤

在这里插入图片描述

代码

class Solution {void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int n){if(n==1){C.push_back(A.back());A.pop_back();return;}dfs(A,C,B,n-1);C.push_back(A.back());A.pop_back();dfs(B,A,C,n-1);}
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {dfs(A,B,C,A.size());}
};
  1. 定义一个私有的递归函数 dfs,该函数将 A 柱上的 n 个盘子通过 B 柱移动到 C 柱。参数 A、B 和 C 分别表示三个柱子的盘子状态,n 表示要移动的盘子数量。
  2. 在递归函数中,当只有一个盘子时,直接将 A 柱的盘子移到 C 柱上,然后返回。
  3. 在递归函数中,先将 A 柱上的 n-1 个盘子通过 C 柱移动到 B 柱上,然后将 A 柱上的最后一个盘子移动到 C 柱上,最后将 B 柱上的 n-1 个盘子通过 A 柱移动到 C 柱上。
  4. 在公有函数 hanota 中,调用递归函数 dfs,传入 A、B、C 三个柱子的状态和盘子数量。

02.合并两个有序链表

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

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0] 

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

思路

这里我们如果划分为子问题,每次就拿出最小的那个节点当做头节点,拼接剩下的当前节点尾部的节点和另一个链表的头节点相比较的更小的点,最后谁被拼接完了,就直接拼接另一条链表剩下的,这样不难看出,每次的步骤都是重复的,于是我们可以使用递归的思想来解决这道问题。

代码

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(!list1) return list2;if(!list2) return list1;if(list1->val<=list2->val){list1->next=mergeTwoLists(list1->next,list2);return list1;}else{list2->next=mergeTwoLists(list2->next,list1);return list2;}}
};
  1. 如果 list1 为空,说明第一个链表为空,直接返回 list2。
  2. 如果 list2 为空,说明第二个链表为空,直接返回 list1。
  3. 接下来比较 list1 和 list2 的头节点的值,选择较小的节点作为新链表的头节点。
  4. 如果 list1 的头节点值小于等于 list2 的头节点值,将 list1 的下一个节点与 list2 合并,并返回 list1 作为新链表的头节点。
  5. 如果 list2 的头节点值小于 list1 的头节点值,将 list2 的下一个节点与 list1 合并,并返回 list2 作为新链表的头节点。

03.反转链表

题目链接:https://leetcode.cn/problems/reverse-linked-list/

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

**进阶:**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

思路

若我们直接遍历到最后的节点再逐个向前改变指向,在每次接入前一个节点时,将它的next指向空,最终返回头节点即可。

  1. 递归函数的含义:交给你⼀个链表的头指针,你帮我逆序之后,返回逆序后的头结点;
  2. 函数体:先把当前结点之后的链表逆序,逆序完之后,把当前结点添加到逆序后的链表后面即可;
  3. 递归出口:当前结点为空或者当前只有⼀个结点的时候,不用逆序,直接返回

代码

class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head||!head->next) return head;ListNode* newhead = reverseList(head->next);head->next->next=head;head->next=nullptr;return newhead;}
};

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

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

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1] 

提示:

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

思路

我们将问题划分为子问题,先交换当前节点的下两个节点,将当前节点的下一个节点作为新的头节点,将当前节点的下一个节点指向递归操作的结果,返回新的头节点。

代码

class Solution {
public:ListNode* swapPairs(ListNode* head) {// 如果链表为空或者只有一个节点,无需交换,直接返回原链表头指针if (!head || !head->next)return head;// 递归调用,交换当前节点的下两个节点ListNode* tmp = swapPairs(head->next->next);// 将当前节点的下一个节点作为新的头节点ListNode* ret = head->next;// 将当前节点的下一个节点指向当前节点,实现交换head->next->next = head;// 将当前节点的下一个节点指向递归操作的结果head->next = tmp;// 返回新的头节点return ret;}
};
  1. if (!head || !head->next):检查链表是否为空或者只有一个节点。如果是,直接返回原链表头指针,因为不需要进行交换。
  2. ListNode* tmp = swapPairs(head->next->next);:递归调用swapPairs函数,传入当前节点的下两个节点。这样就会从链表的末尾开始,每次交换两个相邻的节点,然后返回新的头节点。
  3. ListNode* ret = head->next;:将当前节点的下一个节点作为新的头节点,因为在交换过程中,它会变成新的头节点。
  4. head->next->next = head;:将当前节点的下一个节点指向当前节点,实现交换操作。
  5. head->next = tmp;:将当前节点的下一个节点指向递归操作的结果,即当前节点的下两个节点交换后的头节点。
  6. return ret;:返回新的头节点,作为上层递归调用的结果。

05.Pow(x, n)

题目链接:https://leetcode.cn/problems/powx-n/

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。

示例 1:

输入:x = 2.00000, n = 10
输出:1024.00000

示例 2:

输入:x = 2.10000, n = 3
输出:9.26100

示例 3:

输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25

提示:

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • n 是一个整数
  • 要么 x 不为零,要么 n > 0 。
  • -104 <= xn <= 104

思路

这里我们可以使用二分的思想,可以快速提高效率,例如将3的32次方分为两个3的16次方相乘,不断向下递归,最终返回相乘结果,只不过这里需要注意负数和奇偶次方问题需要单独判断。

代码

class Solution {
public:double myPow(double x, int n) {// 如果指数n为负数,将问题转化为计算 x^(-n),即取倒数return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);}double Pow(double x, long long n) {// 递归终止条件:n为0时,任何数的0次方都为1if (n == 0) return 1.0;// 递归调用,计算 x^(n/2)double tmp = Pow(x, n / 2);// 如果n为奇数,返回 tmp * tmp * xif (n % 2)return tmp * tmp * x;else // 如果n为偶数,返回 tmp * tmpreturn tmp * tmp;}
};
  1. return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);:根据指数n的正负情况,决定调用正指数或者取倒数的递归函数。当n为负数时,将其转化为正数计算,并返回结果的倒数。
  2. double Pow(double x, long long n):递归函数,用于计算 x^n。
  3. if (n == 0) return 1.0;:递归终止条件。当指数n为0时,任何数的0次方都为1。
  4. double tmp = Pow(x, n / 2);:递归调用,计算 x^(n/2)。这里利用了指数幂的性质,将问题规模减半,减少了计算量。
  5. if (n % 2):判断n是否为奇数。
  6. return tmp * tmp * x;:如果n为奇数,返回 tmp * tmp * x,这是因为 x^n = (x(n/2))2 * x。
    n) : Pow(x, n);`:根据指数n的正负情况,决定调用正指数或者取倒数的递归函数。当n为负数时,将其转化为正数计算,并返回结果的倒数。
  7. double Pow(double x, long long n):递归函数,用于计算 x^n。
  8. if (n == 0) return 1.0;:递归终止条件。当指数n为0时,任何数的0次方都为1。
  9. double tmp = Pow(x, n / 2);:递归调用,计算 x^(n/2)。这里利用了指数幂的性质,将问题规模减半,减少了计算量。
  10. if (n % 2):判断n是否为奇数。
  11. return tmp * tmp * x;:如果n为奇数,返回 tmp * tmp * x,这是因为 x^n = (x(n/2))2 * x。
  12. return tmp * tmp;:如果n为偶数,返回 tmp * tmp,这是因为 x^n = (x(n/2))2。

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

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

firewall防火墙配置实战

基本操作 服务启停操作 #停止firewall systemctl stop firewalld #禁止firewall开机启动 systemctl disable firewalld #开启firewall systemctl start firewalld #开机启动防火墙 systemctl enable firewalld # 查看防火墙状态 firewall-cmd --state systemctl status f…

springboot文件上传需要的配置

总结一下文件上传需要的配置信息&#xff1a; ①在springboot的配置文件中指定请求大小及文件大小&#xff0c;默认大小较小&#xff0c;可能不够 spring.servlet.multipart.max-file-size512MB spring.servlet.multipart.max-request-size512MB ②在springboot的配置文件中…

实现VLAN间通信以太网链路聚合与交换机堆叠、集群华为ICT网络赛道

10.实现VLAN间通信 10.1.使用路由器实现VLAN间通信 使用路由器物理接口 路由器三层接口作为网关&#xff0c;转发本网段前往其它网段的流量。 路由器三层接口无法处理携带VLAN Tag的数据帧&#xff0c;因此交换机上联路由器的接口需配置为Access. 路由器的一个物理接口作为一…

easyx devc++ 开发具有导出文件夹DLC的瓦片地图编辑器

1. F1保存为 DLC 输出为当前文件目录下。 2. 瓦片的边框利用绘制到 -1 -1 把边框绘制到外部 3. 利用 1 实现网格保留 #include <graphics.h> #include <stdio.h> #include <string.h> #include <io.h> // 保存游戏地图贴图数据 void savegamemap(in…

python常见的数据类型与数据结构(一)数字类型 字符串类型 布尔类型 列表 集合 字典 的定义与常规操作方法

python常见的数据类型与数据结构&#xff08;一&#xff09;数字类型 字符串类型 布尔类型 列表 集合 字典 的定义与常规操作方法 数据类型数字类型字符串类型布尔类型 数据结构列表集合字典 数据类型 数字类型 数字类型有int(整数)&#xff0c;float(浮点数)和complex(复数型…

异步任务超时机制

目录 1、Thread.Join(timeout) 2、Task.WhenAny(task,Task.Delay(timeout)) 3、WaitAsync(timeout) 需主动取消 4、CancellationTokenSource(timeout) 1、Thread.Join(timeout) var thread new Thread(() > {try {Console.WriteLine("Foo start...");Thread…

vue 使用docx库生成word表格文档

在Vue.js中生成Word表格文档&#xff0c;可以通过前端库来实现。这些库可以帮助我们轻松地将HTML表格转换为Word文档&#xff08;通常是.docx格式&#xff09;。以下是一些流行的前端库&#xff0c;它们可以用于在Vue项目中生成Word表格文档&#xff1a; docx…

保险购买的渠道

买保险的渠道 1.代理人。这个是保险公司传统的渠道&#xff0c;代理人的队伍非常庞大&#xff0c;许多人都碰到过保险代理人。 保险代理人的优势是"线下""1对1"&#xff0c;业务员如果非常专业&#xff0c;就能够给我们提供非常好的体验。由于大多数人接…

跨境电商无货源如何实现自动化对接1688货源商品上架?1688商品采集API来帮你

阿里巴巴集团旗下的B2B电子商务网站&#xff0c;提供海量优质商品&#xff0c;为采购商和供应商提供交流、合作、采购等服务&#xff0c;是很多没有货源优势的电商卖家首选的货源途径&#xff0c;也是国内最大、货源种类最齐全的货源网站。 不少做跨境电商无货源的朋友都想要直…

优思学院|精益思想如何识别价值流?【案例分析】

精益思想是一种为了提高效率、减少浪费的管理哲学&#xff0c;精益思想强调在整个生产过程中识别并消除一切不创造价值的步骤。 价值流分析是精益思想中的一个核心概念&#xff0c;通过深入分析特定产品从原材料到最终交付给顾客的全过程&#xff0c;来识别并削减浪费&#xf…

Win11专业版安装集成了谷歌框架的安卓子系统,包含谷歌商店

1.摘要 上一篇博客讲述了使用微软商店安装安卓子系统的教程 https://blog.csdn.net/RudeTomatoes/article/details/135958882 上述方法的优点是安装过程简单&#xff0c;但是&#xff0c;由于Windows安卓子系统是微软与亚马逊联合开发&#xff0c;默认没有安装谷歌框架。我尝试…

实现一个Windows环境一键启停Oracle的bat脚本

Oracle数据库有许多优点,其中一些最重要的包括: 可靠性和稳定性: Oracle数据库经过长期的发展和测试,被广泛认为是非常可靠和稳定的数据库管理系统。它在大型企业和关键业务环境中被广泛应用,能够处理高负载和大规模的数据。 高性能: Oracle数据库具有优化的查询处理器和…

Pytorch框架-----torch.tensor(创建张量)

文章目录 前言一、torch.Tensor二、构建tensor1.从Python的list或序列构建2.空张量3.索引和切片来获取和修改一个张量tensor中的内容 前言 torch.Tensor 是包的核心类。如果将其属性 .requires_grad 设置为 True&#xff0c;则会开始跟踪针对 tensor的所有操作。完成计算后&am…

线程相关整理

一 常用的线程手段 1 synchronized 有方法&#xff0c;和方法块&#xff0c;新的java版本 内部实现已经包含了多种方案&#xff0c;并动态调整方案&#xff0c;因此不是特别需求的化&#xff0c;建议直接用此方式 2 reentrantlock 可以构造公平锁 以上两种 代码片段应该是没得选…

开箱即用之 redis键值失效通知后端进行业务操作

引入redis依赖 <!--Spring boot Redis--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId> </dependency>配置类编写 import com.alibaba.fastjson.support.sp…

蓝牙攻击工具集合与使用说明

bluez - 蓝牙协议栈&#xff0c;提供了蓝牙设备管理和通信的基本功能。btscanner - 用于发现和扫描蓝牙设备的工具。bluetoothctl - 蓝牙控制终端工具&#xff0c;用于管理蓝牙设备和进行配对等操作。spooftooph - 用于欺骗和伪造蓝牙设备的MAC地址的工具。ubertooth - 用于无线…

设计模式一:单例模式

1、单例模式的实现方式 /*** 1、饿汉模式*/ public class Singleton1 {private static AtomicInteger count new AtomicInteger(0);private static final Singleton1 instance new Singleton1();public static Singleton1 getInstance(){return instance;} }/*** 2、懒汉模式…

学习总结19

# 奶牛的耳语 ## 题目描述 在你的养牛场&#xff0c;所有的奶牛都养在一排呈直线的牛栏中。一共有 n 头奶牛&#xff0c;其中第 i 头牛在直线上所处的位置可以用一个整数坐标 pi(0< pi < 10^8) 来表示。在无聊的日子里&#xff0c;奶牛们常常在自己的牛栏里与其它奶牛交…

设计模式-面试题

一、实际应用 项目中使用到的设计模式 模板方法模式、工厂方法模式、外观模式、建造者模式Spring中使用到的设计模式 代理模式、单例模式、观察者模式二、设计模式分类 设计模式(Design Pattern)是一套被反复使用、代码设计经验的总结。使用设计模式是为了可重用代码、让代码…

vue3项目配置按需自动导入API组件unplugin-auto-import

场景应用&#xff1a;避免写一大堆的import&#xff0c;比如关于Vue和Vue Router的 1、安装unplugin-auto-import npm i -D unplugin-auto-import 2、配置vite.config import AutoImport from unplugin-auto-import/vite//按需自动加载API插件 AutoImport({ imports: ["…