面试题08.06.汉诺塔问题Easy
在经典汉诺塔问题中，有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个。
题解先从简单例子开始思考
假设n=1，直接从A移动到C如果n=2，就要借助B，一共需要3步：最小的盘子移动到B，最大的盘子移动到C，最小的盘子从B移动到C如果n2，把上面n-1个看做一体，就将最初n个盘子从A移动到C→将n-1个盘子从A移动到C。依此类推，直至转换成1个盘子就解决了，这就是分治的思想分治思想就是递归，把大问题分解成若干与原来问题结构相同但规模较小的子问题
n=1时，直接把盘子从A移动到Cn1时2.1先把上面n-1个盘子从A移动到B（子问题，递归）2.2再将最大的盘子从A移动到C2.3再将B上n-1个盘子从B移动到C（子问题，递归）AC代码//递归经典问题classSolution{public:voidhanota(vectorintA,vectorintB,vectorintC){intn=A.size();move(n,A,B,C);}//自定义函数voidmove(intn,vectorintA,vectorintB,vectorintC){if(n==1){C.push_back(A.back());A.pop_back();//删除最后一个元素return;}move(n-1,A,C,B);//移动n-1个盘子从A移动到BC.push_back(A.back());//移动第n个盘子从A到CA.pop_back();//没有这句会WA/*输入：[2,1,0][][]输出：[1,1,0]预期结果：2,1,0]*/move(n-1,B,A,C);//移动n-1个盘子从B移动到C}};复杂度时间复杂度
。一共需要移动的次数空间复杂度
Reference
[1]从0开始数.汉诺塔小游戏和递归思想
[2]
z1m题解：图解汉诺塔的故事预览时标签不可点收录于合集#个上一篇下一篇