LeetCode 面试题 08.06. 汉诺塔问题

Categories:

题目描述
思路分析
1. 解法一：递归搬盘（推荐）
相似题目

题目描述

✅ 面试题 08.06. 汉诺塔问题

思路分析

解法一：递归搬盘（推荐）

核心思路：

将 n 个盘子从 A 移到 C：先将 n-1 个盘子从 A 移到 B，再将最大盘子移到 C，最后将 n-1 个盘子从 B 移到 C。

递归终止条件为 A 只剩 1 个盘子。

复杂度分析：

时间复杂度：O(2^n)，其中 n 表示盘子数量。

空间复杂度：O(n)，递归栈深度为 n。

// 递归搬盘
class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }

    private void move(int n, List<Integer> A, List<Integer> B, List<Integer> C) {
        if (n == 1) {
            C.add(A.remove(A.size() - 1));
            return;
        }
        move(n - 1, A, C, B);
        C.add(A.remove(A.size() - 1));
        move(n - 1, B, A, C);
    }
}

// 递归搬盘
func hanota(A []int, B []int, C []int) []int {
	move(len(A), &A, &B, &C)
	return C
}

func move(n int, A, B, C *[]int) {
	if n == 1 {
		*C = append(*C, (*A)[len(*A)-1])
		*A = (*A)[:len(*A)-1]
		return
	}
	move(n-1, A, C, B)
	*C = append(*C, (*A)[len(*A)-1])
	*A = (*A)[:len(*A)-1]
	move(n-1, B, A, C)
}

相似题目

题目	难度	考察点
剑指 Offer 10- I. 斐波那契数列	简单	递归/DP
46. 全排列	中等	递归
77. 组合	中等	回溯
70. 爬楼梯	简单	递归/DP
509. 斐波那契数	简单	递归/DP
面试题 08.07. 无重复字符串的排列组合	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/32910729