深圳网站建设方维网络,网站建设实施计划,枣庄建设路小学网站,有赞微商城小程序往期文章#xff08;希望小伙伴们在看这篇文章之前#xff0c;看一下往期文章#xff09;
#xff08;1#xff09;递归、搜索与回溯算法#xff08;专题零#xff1a;解释回溯算法中涉及到的名词#xff09;【回溯算法入门必看】-CSDN博客
接下来我会用几道题#…往期文章希望小伙伴们在看这篇文章之前看一下往期文章
1递归、搜索与回溯算法专题零解释回溯算法中涉及到的名词【回溯算法入门必看】-CSDN博客
接下来我会用几道题来让同学们利用我在专题零中提到的递归的宏观思想来解决这些题目。
目录
1. 汉诺塔
2. 合并两个有序链表
3. 反转链表
4. 两两交换链表中的结点
5. 快速幂
解法一 暴力循环
解法二 不断拆分
解法三 利用了二进制的特点 1. 汉诺塔
这道题可以说是递归最经典的题目之一接下来我们就从这道题入手重新认识一下递归是什么
力扣题目链接 解析 总结我们想知道n个盘子的次数记住了在求解f(n)的时候我们直接默认f(n - 1)已经完了就可以了这个在前面已经解释过了在此不再鳌述。我们将n-1个盘子当作一个整体这就是类似于分治求解子问题的思想
那么当由3个盘子时就有公式f(3,x,y,z) f(2,x,z,y),x-z,f(2,y,x,z)当有4个盘子时就有公式f(4,x,y,z) f(3,x,z,y),x-z,f(3,y,x,z).从而推出f(n,x,y,z) f(n,x,z,y),x-z,f(n,y,x,z)!
综上所述也就是说我们想移动n个盘子就需要先移动n - 1个盘子移动n - 1个盘子就需要先移动n - 2个盘子 ………………移动2个盘子就必须先移动1个盘子
1而移动1个盘子就是递归的终止条件
2而n个盘子变成n - 1个盘子就是递归的大问题变成小问题的方法
宏观角度分析递归
再来回顾宏观的细节
一不要在意递归的细节展开图二把递归的函数当成一个“黑盒”三我们的无条件的相信“黑盒”可以为我们解决当前的子问题再次强调递归中的每个子问题的解题步骤都是一样
具体构建一个递归算法
1创建函数头 —— 从重复子问题入手将x柱子上的盘子借助y柱子转移到z柱子上。从而有函数头为dfs(int x,int y,int z,int n); x、y和z代表了柱子n代表现在多少个盘子需要移动。x是开始柱y是中转柱z是目的柱。
2确定函数体 —— 无条件相信他能帮我们解决每一个子问题的。
重复的子问题如下
如从 x 号柱子将n - 1个盘子借助 z 号柱子移动到 y 号柱子上将 x 号柱子将最后一个盘子移动到 z 号柱子上将 y 号柱子上的n - 1个盘子移动到 z 号柱子上
从而有函数体为
① dfs(x,z,y,n - 1); ② x.back - z; ③ dfs(y,x,z,n - 1);
3递归出口当剩下一个盘子的时候也就是n 1时。x.back - z即可。 //宏观角度分析递归//1.创建函数头//2.确定函数体无条件相信他能帮我们解决每一个子问题的//3.递归出口public void hanota(ListInteger A, ListInteger B, ListInteger C) {dfs(A,B,C,A.size());}public void dfs(ListInteger x,ListInteger y,ListInteger z,int size){//递归出口if(size 1){z.add(x.remove(x.size() - 1));return;}//封装一个小黑盒//将x柱上的size - 1个盘子通过z柱子移动到y柱子上dfs(x,z,y,size - 1);//将a柱上的最后一个盘子移动到c柱子上z.add(x.remove(x.size() - 1));//将b柱上的size - 1个盘子通过a柱子移动到c柱子上dfs(y,x,z,size - 1);} 2. 合并两个有序链表
力扣题目链接 解析 1递归函数的含义交给你两个链表的头结点你帮我把它们合并起来并且返回合并后的头结点。 2函数体选择两个头结点中较⼩的结点作为最终合并后的头结点然后将剩下的链表交给递归函数去处理。 3递归出⼝当某⼀个链表为空的时候返回另外⼀个链表。 // 法一递归法public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 递归出口当l1或者l2为空就返回另一个不为空的链表if (l1 null)return l2;if (l2 null)return l1;//如果l1的值小于l2那么就让l1作为头结点剩下的结点继续比较if (l1.val l2.val) {l1.next mergeTwoLists(l1.next,l2);return l1;}else{l2.next mergeTwoLists(l1,l2.next);return l2;}} 3. 反转链表
力扣题目链接 解析
1递归函数的含义交给你⼀个链表的头指针你帮我逆序之后返回逆序后的头结点。 2函数体先把当前结点之后的链表逆序逆序完之后把当前结点添加到逆序后的链表后⾯即可。相同的子问题 3递归出⼝当前结点为空或者当前只有⼀个结点的时候不⽤逆序直接返回。 public ListNode reverseList(ListNode head) {return dfs(head);}public ListNode dfs(ListNode h){//递归出口直接到找最后一个结点类似后序遍历if(h null || h.next null){return h;}//找最后一个结点ListNode newNode dfs(h.next);//从倒数第二个结点开始h.next.next h;h.next null;return newNode;} 4. 两两交换链表中的结点
力扣题目链接 解析
1递归函数的含义交给你⼀个链表将这个链表两两交换⼀下然后返回交换后的头结点。 2函数体先去处理⼀下第⼆个结点往后的链表然后再把当前的两个结点交换⼀下连接上后⾯处理后的链表。相同的子问题 3递归出⼝当前结点为空或者当前只有⼀个结点的时候不⽤交换直接返回。 //后序遍历public ListNode swapPairs(ListNode head) {//链表中节点的数目在范围 [0, 100] 内//如果只剩下一个结点就没必要交换了因为是两两交换if(head null || head.next null){return head;}//先去交换在我之后之后的结点ListNode newNode swapPairs(head.next.next);ListNode ret head.next;head.next newNode;ret.next head;return ret;} 要先修改后面结点再能修改当前结点很类似后序遍历的方式。 5. 快速幂
力扣题目链接 解法一 暴力循环 public double myPow(double x, int n) {double ret 1;int tmp n;if(n 0) n -n;for(int i 1;i n;i){ret * x;}if(tmp 0) ret 1.0 / ret;return ret;} 暴力循环可以解决较小的幂当幂的值比较大就会报超时的错误 所以有了如下两个改进方案 解法二 不断拆分
1递归函数的含义求出 x 的 n 次⽅是多少然后返回。 2函数体先求出 x 的 n / 2 次⽅是多少然后根据 n 的奇偶得出 x 的 n 次⽅是多少。 3递归出⼝当 n 为 0 的时候返回 1 即可 。 //第二种方法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;} 解法三 利用了二进制的特点
例如算:
分解
1而、、是倍乘关系所以算不用11个a相乘而是 得到而 得到。
2那么问题来了如何将11分解成 11 8 2 1这样的倍乘关系呢
答
3这里因为二进制的11中第三位为0所以没有 如果跳过4呢1011中的0就是需要跳过的 4。
4
推算乘积从低位往高位处理1011右移一次就把刚处理的低位移走了
1011处理末尾的1计算a。 1011处理第2个1计算。 1011处理0跳过。1011处理1计算。 。 //第三种方法public double myPow(double x, int n) {double base x;int tmp n;double res 1;if(n 0) n -n;while(n ! 0){if((n 1) ! 0) //如果n的最后一位是1表示这个地方需要乘res*base;base*base;//推算乘积在解析有说明n1;//n右移一位把刚处理过n的最后一位去掉}if(tmp 0) res 1.0 / res;return res;} 注解法三的速度比解法一快了许多但是相比于解法二还是慢了一些导致超时错误。
