百度竞价代运营托管,广告开户南京seo,家乡网站怎么做,女人和男人做爰网站#x1f525;个人主页#xff1a; 中草药 #x1f525;专栏#xff1a;【算法工作坊】算法实战揭秘 #x1f347;一.递归
概念
递归是一种解决问题的方法#xff0c;其中函数通过调用自身来求解问题。这种方法的关键在于识别问题是否可以被分解为若干个相似但规模更小… 个人主页 中草药 专栏【算法工作坊】算法实战揭秘 一.递归
概念
递归是一种解决问题的方法其中函数通过调用自身来求解问题。这种方法的关键在于识别问题是否可以被分解为若干个相似但规模更小的子问题。递归函数有两个主要组成部分
基本情况Base Case这是递归调用的终止条件。每个递归函数都必须有一个或多个明确的基本情况否则递归将无限进行下去。递归步骤Recursive Step这是函数调用自身的部分。在此步骤中问题被分解为更小的子问题然后递归地求解这些子问题。 递归的本质可以理解为 可以把一个主问题拆分成若干个相同的子问题 宏观的理解递归 递归其实是比较抽象的一种算法完全熟练的运用它需要时间的积累与深入的理解因此我们可以学会宏观的去看待递归帮助我们去解决算法问题 1.不必过分关注递归的细节展开图 2.把递归的函数看做一个黑盒不去深究 3.相信这个黑盒一定能完成这个任务 用法
如何写好一个递归
先找到相同的子问题---函数头的设计只关心某一个子问题是如何解决的---函数体的书写注意一下递归函数的出口
应用场景
递归非常适合处理以下类型的问题
分治法问题可以被分解为独立且较小的子问题。树形结构例如文件系统的目录树、DOM树等。回溯算法如八皇后问题、迷宫寻路等。 二. 面试题 08.06. 汉诺塔问题 题目链接面试题 08.06. 汉诺塔问题 代码 public void hanota(ListInteger A, ListInteger B, ListInteger C) {dfs(A,B,C,A.size());return;}public void dfs(ListInteger A, ListInteger B, ListInteger C,int n){//算法的出口if(n1){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);} 算法原理 汉诺塔问题是递归问题的一个经典问题和常规问题一样拆分成细小的步骤 汉诺塔问题通常有三个柱子A、B、C以及n个不同大小的圆盘初始时所有的圆盘都堆叠在柱子A上要求将它们全部移动到柱子C上但在移动过程中必须遵守以下规则
每次只能移动一个圆盘。在任何时刻一个较大圆盘都不能放在较小圆盘上面
代码详解
hanota 方法是主入口点它接受三个列表作为参数分别代表三个柱子A、B、C。dfs 方法是一个递归函数它接受四个参数柱子A、B、C以及当前要移动的圆盘数量n。当n 1时这是递归的基本情况直接将A上的最后一个圆盘移动到C。对于n 1的情况首先递归地将n-1个圆盘从A借助B移动到C然后将A上的最后一个圆盘直接移动到C最后再递归地将n-1个圆盘从B借助A移动到C。 三. 21.合并两个有序链表 题目链接21.合并两个有序链表 代码 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//不能用elseif(list1null){return list2;}if(list2null){return list1;}if(list1.vallist2.val){list1.nextmergeTwoLists(list1.next,list2);return list1;}else{list2.nextmergeTwoLists(list1,list2.next);return list2;}} 算法原理
特殊情况处理首先检查输入的两个链表list1和list2是否为空。 如果list1为空则直接返回list2。如果list2为空则直接返回list1。递归合并如果两个链表都不为空则比较当前节点的值。 如果list1的当前节点值小于等于list2的当前节点值那么将list1的next指向list1.next和list2的合并结果并返回list1。否则将list2的next指向list1和list2.next的合并结果并返回list2。
这段代码使用了递归的方式来合并两个有序链表。其基本思想是
基本情况如果其中一个链表为空那么合并的结果就是另一个链表。递归步骤如果两个链表都不为空则比较当前节点的值。 如果list1的当前节点值小于等于list2的当前节点值那么list1将成为合并后链表的一部分然后递归地去合并list1的下一个节点和list2。如果list2的当前节点值小于list1的当前节点值那么list2将成为合并后链表的一部分然后递归地去合并list1和list2的下一个节点。
四. 206.反转链表
代码 public ListNode reverseList(ListNode head) {if(headnull||head.nextnull){return head;}ListNode newHeadreverseList(head.next);//逆置head.next.nexthead;head.nextnull;return newHead;} 算法原理
这里可以比较这道题的 迭代代码 加深理解
public ListNode reverseList1(ListNode head) {if(headnull){return head;}ListNode curhead.next;head.nextnull;while(cur!null){ListNode curncur.next;cur.nexthead;headcur;curcurn;}return head;} 基本情况如果当前节点head为空或者当前节点是链表的最后一个节点即head.next null那么直接返回head。这是因为如果链表为空或者只剩一个节点就不需要反转了直接返回即可。 递归步骤如果当前节点不是最后一个节点递归地反转head.next即反转当前节点之后的所有节点。这里newHead将是反转后的新头节点即原来链表的最后一个节点成为了新的头节点。 链接反转在递归调用返回后将当前节点head连接到新头节点newHead后面。这一步是通过将head.next.next head;来实现的即将head插入到新反转链表的头部。 注意这里的head.next是原来链表中的下一个节点现在它已经是反转链表的头节点了所以我们通过head.next.next来访问原来链表的下下个节点现在变成了反转链表的第二个节点。 断开连接将head的next设为null这样原来的链表就被切断了从而完成了反转。
五. 24.两两交换链表中的节点 题目链接24.两两交换链表中的节点 代码 public ListNode swapPairs(ListNode head) {if(headnull||head.nextnull){return head;}ListNode tmpswapPairs(head.next.next);ListNode rethead.next;ret.nexthead;head.nexttmp;return ret;}
算法原理
此代码建议先用一个小链表模拟实现以下该过程帮助理解这个递归 基本情况如果当前节点head为空或head.next为空即链表为空或只有一个节点则直接返回head。这是因为单个节点或空链表无需交换。
递归步骤
首先递归地调用swapPairs(head.next.next)这意味着我们假设head.next.next之后的部分已经被正确地交换好了。递归的目的是处理当前节点之后的所有节点。tmp变量存储了从head.next.next开始的交换好的链表部分。ret变量存储了head.next即当前节点的下一个节点它将成为新的头节点。接下来将ret.next设置为head这样就实现了head和head.next这两个节点的交换。最后将head.next设置为tmp这样就将剩余部分的链表正确地连接到了交换后的两个节点之后。 六. 50.Pow(x,n) 题目链接50.Pow(x,n) 代码
public double myPow(double x, int n) {//存在负数情况若为负数变为倒数return n0?1/pow(x,-n):pow(x,n);}public double pow(double x,int n){if(n0){return 1;//相当于x的0次方幂}double tmppow(x,n/2);//若为奇数还需要在 * 上一个xreturn n%20?tmp*tmp:tmp*tmp*x;}
算法原理 当拿到这道题大多数人首先会想到循环但问题是常规的这种循环会超时因此我们应该将问题用递归的方式去简化拆分成相同的子问题 这个算法采用了分治的思想通过递归地将问题规模减半来快速计算幂。
基本情况当n为0时任何数的0次幂都是1。递归步骤 如果n是偶数那么x^n可以表示为(x^(n/2))^2。如果n是奇数那么x^n可以表示为x * (x^(n-1))。
通过递归地计算x^(n/2)我们可以将问题规模减半从而大大减少了计算次数。这种方法的时间复杂度大约是O(log n)相比直接循环相乘的O(n)复杂度要高效得多。
