如何做一个属于自己的网站,怎么编辑自己的网站,网站的站外优化,外网登录 wordpress目录
简介#xff1a;
递归问题解题的思路模板
例题1#xff1a;汉诺塔
例题2#xff1a;合并两个有序链表
例题3#xff1a;反转链表
例题4#xff1a;两两交换链表中的节点
例题5#xff1a;Pow#xff08;x,n#xff09;-快速幂
结语#xff1a; 简介…目录
简介
递归问题解题的思路模板
例题1汉诺塔
例题2合并两个有序链表
例题3反转链表
例题4两两交换链表中的节点
例题5Powx,n-快速幂
结语 简介
本系列将会带大家深入理解搜索中的一大分支深搜深搜是离不开递归的和回溯思想的优化需要剪枝故我会在例题中详细指出解决这一系列问题的思考思路和解题技巧。
那么我们就从递归开始深搜的基础也就是本文中主要介绍的。
什么是递归
简单来说就是函数自己调用自己。
为什么会用到递归
大问题可以拆解成相同的子问题且子问题的解法和大问题的一模一样这是就可以用到递归。 在解决⼀个规模为n的问题时如果满⾜以下条件我们可以使用递归来解决 a. 问题可以被划分为规模更⼩的⼦问题并且这些⼦问题具有与原问题相同的解决⽅法。 b. 当我们知道规模更⼩的⼦问题规模为n-1的解时我们可以直接计算出规模为n的问题的解。 c. 存在⼀种简单情况或者说当问题的规模⾜够⼩时我们可以直接求解问题。 ⼀般的递归求解过程如下 a. 验证是否满⾜简单情况。 b. 假设较⼩规模的问题已经解决解决当前问题。 上述步骤可以通过数学归纳法来证明。
如何理解递归
不要太在意细节相信函数。
递归问题解题的思路模板
当然在设计递归函数之前最重要的是你要你的递归函数干嘛。 1.递归函数的作用 2.相同子问题------------函数头 3.只关心某一个子问题是如何解决的------------函数体 4.递归出口 建议友友在写递归类型的题目是一定要把这三个地方考虑清楚了再下手。
最后就是相信函数。
例题1汉诺塔
链接汉诺塔
题目简介
递归问题非常经典的一道题目在经典汉诺塔问题中有 3 根柱子及 N 个不同大小的穿孔圆盘盘子可以滑入任意一根柱子。一开始所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。
请编写程序用栈将所有盘子从第一根柱子移到最后一根柱子。 解法 我们可以看到每次都可以把大问题分解成相同的子问题且子问题的解决方法和大问题的一模一样故我们可以使用递归来处理。
1.递归函数的作用
函数作⽤将A中的上⾯n个盘⼦挪到C中。这里的A和C是函数参数的A和C不是实际的很重要。
2.相同子问题函数头
我们要设计一个函数头来完成汉诺塔的递归过程我们可以看到我们需要三根柱子和要记录下来还剩下几个盘子。故我们的函数头可以设计成public void dfs(ListInteger a, ListInteger b, ListInteger c, int n)。关于ListInteger如果友友还没有学到的话可以把他看成一个数组。
3.只关心某一个子问题是如何解决的函数体
我们取第三层汉诺塔来研究大问题被拆成3层汉诺塔。 我们发现子问题刚来三件事
1.把A上面n - 1 个盘子通过C移动到B
2.把A上面最后一个盘中移动到C
3.把B上面n - 1个盘中通过A 移动到C
dfs(a, c, b, n - 1);
c.add(a.remove(a.size() - 1));//这里是因为给出的例题这样做就是把盘中从A移动到C理解思路即可
dfs(b, a, c, n - 1);
4.递归出口
当问题的规模变为n1时即只有⼀个盘⼦时我们可以直接将其从A柱移动到C柱。
本例题代码实现如下
class Solution {public void hanota(ListInteger A, ListInteger B, ListInteger C) {dfs(A,B,C,A.size());}public void dfs(ListInteger A, ListInteger B, ListInteger C,int n ){if(n 1){C.add(A.remove(A.size() - 1));return;}dfs(A,C,B,n - 1);C.add(A.remove(A.size() - 1));dfs(B,A,C,n - 1);}
}
关于本例题要注意的点c.add(a.remove(a.size() - 1));可能有的友友会纠结为什么不是remove0呢其实自己模拟一下即可我们移走盘子是从最上面那个盘子开始移动的。
不用太深究函数的细节陷入将无法自拔如果是第一次的话可以去b站上看看递归的全过程细节这里的不用深究是建立在已经对它的展开有一定理解了第一次学汉诺塔的话我还是建议大家可以看看别人推的整个过程理解更加深刻。
例题2合并两个有序链表
链接合并两个有序链表
题目简介
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解法
通过分析题目我们发现可以把大问题拆成下图的子问题上面的1已经合并有序现在要让24和下面链表合并有序。 故我们可以用递归来解决这道问题。
1.递归函数的作用
交给你两个链表的头结点你帮我把它们合并起来并且返回合并后的头结点.
2.相同子问题函数头
由上图可以看到函数要包含两个链表还要能返回合并后的链表故函数头设定为public ListNode mergeTwoLists(ListNode l1, ListNode l2)
3.只关心某一个子问题是如何解决的函数体
选择两个头结点中较小的结点作为最终合并后的头结点然后将剩下的链表交给递归函数去处理。
4.递归出口
当某⼀个链表为空的时候返回另外⼀个链表。
代码如下
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(list1,list2.next);return list2;}}
}
例题3反转链表
链接反转链表
题目简介
给你单链表的头节点 head 请你反转链表并返回反转后的链表。 解法
要想让1到5逆序可以让5逆序后让1到4逆序一直这样下去我们不难发现这就是递归。
1.递归函数的作用
交给你⼀个链表的头指针你帮我逆序之后返回逆序后的头结点。
2.相同子问题函数头
需要传入链表5节点逆序后要把逆序后的新头节点返回故将函数体设为public ListNode reverseList(ListNode head)
3.只关心某一个子问题是如何解决的函数体
先把当前结点之后的链表逆序逆序完之后把当前结点添加到逆序后的链表后⾯即可。
4.递归出口
当前结点为空或者当前只有⼀个结点的时候不⽤逆序直接返回。
代码如下
class Solution {public ListNode reverseList(ListNode head) {ListNode newHead head;if(head null){return head;}ListNode cur head.next;ListNode prev head;head.next null;while(cur ! null){ListNode next cur.next;cur.next prev;prev cur;cur next;}return prev;}
}
例题4两两交换链表中的节点
链接两两交换链表中的节点
题目简介
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 解法:
我们通过阅读题目可以发现要使整个链表两两交换 可以将大问题分为把1和2后面的节点两两交换把一二交换即可同理3和4也是同样的处理思路。
1.递归函数的作用
交给你⼀个链表将这个链表两两交换⼀下然后返回交换后的头结点
2.相同子问题函数头
需要传入原始链表和返回新的头节点故设计为public ListNode swapPairs(ListNode head)
3.只关心某一个子问题是如何解决的函数体
先去处理⼀下第⼆个结点往后的链表然后再把当前的两个结点交换⼀下连接上后面处理后的链表
4.递归出口
当前结点为空或者当前只有⼀个结点的时候不⽤交换直接返回。
代码如下
class Solution {public ListNode swapPairs(ListNode head) {if(head null || head.next null){return head;}ListNode newHead head.next;head.next swapPairs(head.next.next);newHead.next head;return newHead;}
}
例题5Powx,n-快速幂
链接Powx,n
题目简介
实现 pow(x, n) 即计算 x 的整数 n 次幂函数即xn 。 解法
这题不能使用1个1个数的分离递归会超时我们这里要采用二分的思路具体实现如下
1.递归函数的作用
求出x 的n 次⽅是多少然后返回
2.相同子问题函数头
需要传入需要n次方的x和n还要将其返回public double pow(double x, int n)
3.只关心某一个子问题是如何解决的函数体 先求出x 的n / 2 次⽅是多少然后根据n 的奇偶得出x 的n 次⽅是多少
4.递归出口
当n 为0 的时候返回1 即可。
代码如下
最上面要区分一下正负数的区别即可。
class Solution {public double myPow(double x, int 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;}
}
总结本文章是搜索回溯的第一篇带大家再复习了一下递归后续的章节会带领大家深度理解深搜和回溯算法。
结语
其实写博客不仅仅是为了教大家同时这也有利于我巩固自己的知识点和一个学习的总结由于作者水平有限对文章有任何问题的还请指出接受大家的批评让我改进如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注这可以激励我写出更加优秀的文章。
