关于递归的若干算法v2.0

1、面试题 08.06. 汉诺塔问题

将汉诺塔和递归联系起来：

 当n==1时，移动逻辑：

当n==2时。移动逻辑：

当n==3时，逻辑如下：

        将上面两个看做一个整体，将该整体移动到b，将a上最后一个移动到c，然后将b上的两个整体移动到c上的过程可以看做是之前n==2的整个移动过程。

        所以上面的问题可以总结为递归问题。解法如下：

1、重复问题->函数头：

        将a柱子上的n个盘子借助b柱子，移动到c柱子上面；

        dfs（a,b,c,int n）

 2、只关心一个子问题->函数体

        dfs（a,c,b,n-1）;

        a.back->c;

        dfe(b,a,c,n-1);

3、递归的出口 n=1； 

 代码如下：

class Solution {
    public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {
        dfs(a,b,c,a.size());
    }
    public void dfs(List<Integer> a, List<Integer> b, List<Integer> 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);
    }
}

2. 合并两个有序链表

 

1、重复子问题：函数头的设计

        不停地合并两个有序链表：

        node*dfs(l1,l2)

2、只关心某一个问题是在做什么事：函数体的设计

        1)、比较大小，两个指针节点的大小

        2）l1.next=dfs(l1.next,l2)

        3)、return l1

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 l1, ListNode  l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val <= l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

1. 206. 反转链表

视角一： 

1、让当前节点后面的链表先逆置，并且把头结点返回

2、让当前节点添加到逆置后的链表的后面即可

视角二：将链表看成一棵树 

 链表的逆置操作可以看成树的后序遍历

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newlistNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newlistNode;
    }
}

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

class Solution {
    public ListNode swapPairs(ListNode head) {
       if(head == null || head.next == null){
        return head;
       }
       ListNode tmp = swapPairs(head.next.next);
       ListNode ret = head.next;
       ret.next = head;
       head.next = tmp;
       return ret; 
    }
}

50. Pow(x, n)

大致思路如下：

 

1、相同子问题int pow（x，n）

2、函数体tmp = pow（x，0.5n）

return n%2==0？tmp*tmp：tmp*tmp*x

3、递归出口：

        n==0，return 1；

细节问题：

1、n为负数：

2、无穷大。将int强转为long

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;
        }
        double tmp = pow(x,n/2);
        return n%2== 0 ? tmp*tmp :tmp*tmp*x;
    }
}

ps:谢谢观看！！！

原文地址：https://blog.csdn.net/2202_76101487/article/details/145121059

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！