题解 | 汉诺塔问题
解题思路
-
递归思想：
- 将
个盘子的移动分解为三步
- 先将
个盘子移到中间柱子
- 再将最大的盘子移到目标柱子
- 最后将
- 将
-
基本情况：
- 当
时，直接移动这个盘子
- 记录移动步骤
- 当
-
递归过程：
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次
- 总共有
空间复杂度：
- 需要存储所有移动步骤
- 递归调用栈的深度为
注意事项
-
字符串格式：
- 移动描述必须符合要求格式
- "move from X to Y"
-
递归终止条件：
-
参数传递：
- 需要正确传递三个柱子的名称
- 保持移动顺序的正确性
