【DFS】草木蔓发，春山可望 - 1. 递归

用户11369350

发布于 2025-03-12 09:21:25

4800

代码可运行

文章被收录于专栏：Java,后端开发,网站开发,数据结构,算法分析.Java,后端开发,网站开发,数据结构,算法分析.

运行总次数：0

代码可运行

本篇博客给大家带来的是DFS深度优先遍历的解法技巧,本篇文章的题目主要讲递归,在后续的文章中题目会涉及到回溯和剪枝,遇到了一并讲清楚. 🐎文章专栏: DFS 🚀若有问题评论区见 ❤ 欢迎大家点赞评论收藏分享

1. 汉诺塔问题

题目链接: 面试题 08.06. 汉诺塔问题

题目内容: 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例 1：

输入：A = [2, 1, 0], B = [], C = [] 输出：C = [2, 1, 0] 示例 2：

输入：A = [1, 0], B = [], C = [] 输出：C = [1, 0] 提示：

A 中盘子的数目不大于 14 个。

一. 分析题意

假设三根柱子分别为A,B,C 当只有一个盘子,即N = 1时,将A中的盘子直接放到C即可.

当N = 2时, 先将A最上面的盘子放到B上, 再将A最下面的盘子放到C上,最后B上的盘子也放到C上.

当N = 3时, 先将A的上面两个盘子放到B上, 再将A最下面的盘子放到C, 最后将B上两个盘子放到C.

在N=2时,我们就是将两个盘子放到从一个柱子放到另一根柱子的. 在N = 3的时候也重复了N=2时的动作. N = 4时, 重复了N=3时的动作.

分析题意时,发现了重复的子问题, 故可以利用递归来解决这道问题.

二. 写递归代码的具体步骤

① 重复子问题(函数头) 将x柱子上的一堆盘子,借助y柱子转移到z柱子上. void dfs(x,y,z,int n)

② 只关心子问题在做什么(函数体) dfs(x,z,y,n-1) x.remove(x.size()-1) -> z 将x柱子上最后一个盘子删除并移到z上. dfs(y,x,z,n-1)

③ 递归出口当N = 1时, 将x上的盘子移到z上.

三. 代码实现

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. 合并两个有序链表

题目链接: 21. 合并两个有序链表

题目内容: 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 示例 2：

输入：l1 = [], l2 = [] 输出：[] 示例 3：

输入：l1 = [], l2 = [0] 输出：[0]

提示：

两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按非递减顺序排列

一. 写递归代码步骤:

① 重复子问题(函数头) 子问题就是合并两个有序链表,ListNode dfs(list1,list2)

② 只关心子问题在做什么(函数体) 如果list1.val <= list2.val 那就把list1放在list2的前面list1.next = dfs(list1.next,list2),保证升序. 否则反之

③ 递归出口当list1和list2都为null时, return null; 当有一个为null时, return 不为null的那一个.

二. 具体代码实现:

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        return dfs(list1,list2);
    }
    public ListNode dfs(ListNode list1, ListNode list2) {
        if(list1 == null && list2 == null) {
            return null;
        }
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        if(list1.val <= list2.val) {
            list1.next = dfs(list1.next,list2);
            return list1;
        }else {
            list2.next = dfs(list1,list2.next);
            return list2;
        }
    }
}