【算法】递归入门

三三是该溜子

发布于 2025-02-16 19:19:33

7200

代码可运行

文章被收录于专栏：该溜子的专栏该溜子的专栏

运行总次数：0

代码可运行

本篇文章主要是提供递归入门的简单算法题，可以帮助刚接触递归的友友们打开思路，打开递归的大局观，题目不难，重在思想

一：汉诺塔问题

心得感悟：汉诺塔问题是递归系列中最经典的一个问题，我们在思考递归问题的时候，尽量从宏观角度去考虑，包括函数体的设计，方法的出口，递归的调用，相信递归

这道题涉及到的集合的操作：.remove()和.add() 移除元素返回值就是该元素

找重复子问题是递归的核心

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));//这里不能写成a.get(0),因为需要移除来在，放进去
        // c.add(a.get(0));
        dfs(b,a,c,n-1);
    }
}

二：合并两个有序链表

心得感悟：这道题的核心也在于找到重复子问题——选取头结点中val值小的那个作为头结点a，再把剩下的两部分交给递归方法（相信这个方法能把剩下的两部分链表有序连接）合并成一个链表，a.next = 这个递归方法即可，不要深究！！，递归就是理解了问题，代码就会书写就会变得非常优雅。

/**
 * 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 list1, ListNode list2) {
        // 递归出口
        if(list1 == null) return list2;
        if(list2 == null) return list1; 
        // 1:选取，头结点中值较小的那个
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list2.next,list1);
            return list2;
        }
    }
}

三：反转链表

心得：

1：递归的出口，if条件为什么是head == null 和head.next == null 两个条件要想清楚，在代码注释中已经详细解释，

2：关键点：整体思想，头结点的记录

/**
 * 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 reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = reverseList(head.next);//记录一下头结点//这里head可能为null，为null就不递归了
        head.next.next = head;//这一步是关键，尽管把head的右边看为了整体，还得用head.next来表示这个整体。这里是head.next可能为null,
        head.next = null;
        return node;
    }
}

四：两两交换链表中的节点

心得：

1：大局观写这个代码4行搞定，太爽了

2：重复子问题解决之后，对于指正的记录是非常讲究的，

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 swapPairs(ListNode head) {
        if(head == null || head.next == null){//如果当前节点为null或者只有一个节点，就返回
            return head;
        }
        //后面整体进行交换，然后用一个指针记录一下头结点
        ListNode tmp = swapPairs(head.next.next);
        // 最后需要返回的节点也要记录一下
        ListNode result = head.next;
        result.next = head;
        head.next = tmp;
        return result;
    }
}

迭代版本

/**
 * 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 swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 虚拟头结点
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        // 先搞四个指针
        ListNode prev = newHead, cur = prev.next, next = cur.next, nnext = next.next;
        while (cur != null && next != null) {
            prev.next = next;
            next.next = cur;
            cur.next = nnext;

            prev = cur;
            cur = nnext;
            if (cur != null) {
                next = cur.next;
            }
            if (next != null) {
                nnext = next.next;
            }
        }
        return newHead.next;

    }
}

五：快速幂

50. Pow(x, n)

当发生溢出情况的时候，可以转化为long，在递归传参的时候，我们可以先除2，然后再强制向下转型，这样就不会溢出了我嘞个乖乖，折磨

溢出版本

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if(N == 0) return 1.0;
        if(N < 0){
            x = 1/x;
            N = -N;
        }
        double tmp = myPow(x,(int)(N/2));
        return N % 2 == 0 ? Math.pow(tmp,2) : Math.pow(tmp,2)*x;
    }
}

非溢出版本

class Solution {
    public double myPow(double x, int n) {
        return n >= 0 ? pow(x,n) : 1/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 ? Math.pow(tmp, 2) : Math.pow(tmp, 2) * x;
        // return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-15，如有侵权请联系 cloudcommunity@tencent.com 删除

链表