题目描述：在经典汉诺塔问题中，有 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个。
解题思路：通过纸和笔进行实际的“搬运”工作
1. A盘中数目为0，无需搬运， 操作步数为：0（2^0 - 1）
2. A盘中数目为1，A->C，操作步数为：1（2^1-1）
3. A盘中数目为2，需要将A盘中最上面的圆盘先放入B柱，然后将A盘中底部大圆盘放入C，然后再将B中的小圆盘放入C即完成，即 A->B, A->C, B->C, 操作步数为：3（2^2-1）
4. 同理，A盘中数目为3时，A->C, A->B, C->B, A->C, B->A, B->C, A->C, 操作步数为：7（2^3-1）
...
通过以上步骤我们发现，回顾整个搬运过程，如果想将n个从小到大排列的圆盘从A柱搬运到C柱，并且保持排列顺序不变，需要先将A柱上面的n-1个圆盘经过C柱的搬运到B柱上，也就是说，将A柱最大圆盘搬运到C柱的时候，此时B柱上是从小到大排列的n-1个圆盘，即可以将A柱最大圆盘搬运到C柱的时刻，三根柱子的情况是：A柱剩最大圆盘，B柱n-1圆盘（从小到大排列），C柱为空，这样就可以想象成： A(n-1)->B, A->C, B->C，其中A(n-1)->B过程需要经过C柱， B->C过程需要经过A柱
解题语言： Swift
class Solution {
func hanota(_ A: inout [Int], _ B: inout [Int], _ C: inout [Int]) {
let n = A.count
recursion(&A, &B, &C, n)
}
func recursion(_ A: inout [Int], _ B: inout [Int], _ C: inout [Int], _ n: Int) {
if n <= 0 {
return
}
if n == 1 {
let val = A.removeLast()
C.append(val)
return
}
//将A上面的 n-1 个圆盘经由 C 移到 B
recursion(&A, &C, &B, n - 1)
//将A最底部的盘移动到C
let val = A.removeLast()
C.append(val)
//将B上面的 n-1 个圆盘经 A 移动到 C
recursion(&B, &A, &C, n - 1)
}
}
复杂度分析：
时间复杂度：O(2n)，其中n为圆盘数目，因为将n个圆盘从A->C需要经过2n-1步
空间复杂度: O(n), 其中n为圆盘数目，空间复杂度主要取决于递归调用的栈空间，因为递归需要保存调用栈，直至递归完成，递归最大深度为n，
