解题思路

  1. 递归思想：

    • 将 个盘子的移动分解为三步
    • 先将 个盘子移到中间柱子
    • 再将最大的盘子移到目标柱子
    • 最后将 个盘子从中间移到目标柱子

  2. 基本情况：

    • 当 时，直接移动这个盘子
    • 记录移动步骤

  3. 递归过程：

    hanoi(n, from, mid, to):
    if n == 1:
        move disk from 'from' to 'to'
        return
    hanoi(n-1, from, to, mid)
    move disk n from 'from' to 'to'
    hanoi(n-1, mid, from, to)

代码

class Solution {
public:
    vector<string> getSolution(int n) {
        vector<string> steps;
        hanoi(n, "left", "mid", "right", steps);
        return steps;
    }
    
private:
    void hanoi(int n, string from, string mid, string to, vector<string>& steps) {
        if(n == 1) {
            steps.push_back("move from " + from + " to " + to);
            return;
        }
        
        hanoi(n-1, from, to, mid, steps);
        steps.push_back("move from " + from + " to " + to);
        hanoi(n-1, mid, from, to, steps);
    }
};

import java.util.*;

public class Solution {
    private ArrayList<String> steps;
    
    public ArrayList<String> getSolution(int n) {
        steps = new ArrayList<>();
        hanoi(n, "left", "mid", "right");
        return steps;
    }
    
    private void hanoi(int n, String from, String mid, String to) {
        if(n == 1) {
            steps.add("move from " + from + " to " + to);
            return;
        }
        
        // 将n-1个盘子从from移动到mid
        hanoi(n-1, from, to, mid);
        // 将第n个盘子从from移动到to
        steps.add("move from " + from + " to " + to);
        // 将n-1个盘子从mid移动到to
        hanoi(n-1, mid, from, to);
    }
}

class Solution:
    def getSolution(self, n: int) -> List[str]:
        steps = []
        
        def hanoi(n: int, fr: str, mid: str, to: str) -> None:
            if n == 1:
                steps.append(f"move from {fr} to {to}")
                return
            
            hanoi(n-1, fr, to, mid)
            steps.append(f"move from {fr} to {to}")
            hanoi(n-1, mid, fr, to)
        
        hanoi(n, "left", "mid", "right")
        return steps

算法及复杂度分析

算法：递归 时间复杂度：

  • 每个盘子都需要移动3次
  • 总共有 个盘子

空间复杂度：

  • 需要存储所有移动步骤
  • 递归调用栈的深度为

注意事项

  1. 字符串格式：

    • 移动描述必须符合要求格式
    • "move from X to Y"

  2. 递归终止条件：

    • 时直接移动并记录

  3. 参数传递：

    • 需要正确传递三个柱子的名称
    • 保持移动顺序的正确性