难度: 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]
提示:
运行时间: 16 ms
内存: 16.1 MB
class Solution:
def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
"""
Do not return anything, modify C in-place instead.
"""
if len(A) == 1:
C.append(A[0])
A.pop()
return
self.hanota(A[1:], C, B)
C.append(A[0])
A.pop()
C += B
B.clear()
本题解采用了经典的递归方法来解决汉诺塔问题。递归方法分为几个步骤：1. 将顶部的n-1个盘子从源柱子A使用辅助柱子C移动到目标柱子B。2. 将最大的盘子直接从源柱子A移动到目标柱子C。3. 最后，将那n-1个盘子从B通过A移动到C。递归的基础情况是当只有一个盘子时，直接将其从A移动到C。
时间复杂度: O(2^n)
空间复杂度: O(n)
class Solution:
def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
\"\"\"
Do not return anything, modify C in-place instead.
\"\"\"
if len(A) == 1:
C.append(A[0]) # 将A的最后一个元素加到C中
A.pop() # 移除A中的最后一个元素
return
self.hanota(A[1:], C, B) # 将A中除了最后一个元素之外的元素递归移动到B
C.append(A[0]) # 将A的最后一个元素加到C中
A.pop() # 移除A中的最后一个元素
C += B # 将所有在B中的元素移动到C中
B.clear() # 清空B
在汉诺塔问题中，移动n-1个盘子到辅助柱子B是为了释放最大的盘子，并将其直接从源柱子A移动到目标柱子C。如果直接尝试将n-1个盘子移动到目标柱子C，那么最大的盘子将无法直接移动到C，因为它被其他较小的盘子所阻挡。因此，先将n-1个盘子移动到B，然后移动最大盘子到C，最后将这n-1个盘子从B移动到C，这样可以确保按正确顺序和规则解决问题。
代码`self.hanota(A[1:], C, B)`的含义是将列表A中除了最后一个元素之外的所有元素视为一个独立的子问题，并使用C作为辅助柱子，B作为目标柱子来递归解决这个子问题。此处的递归调用是基于汉诺塔问题的可归约性：解决包含n个盘子的问题可以通过先解决n-1个盘子的问题来简化。这里A[1:]表示除去最底下盘子后的所有盘子，递归地先将它们从A移到B，以便可以处理最底下的最大盘子。
当A中只有一个盘子时，解决方案是直接将这个盘子从A移到C。这是递归的基础情况。在代码中，如果A的长度为1，就将A的元素移到C，并从A中移除这个元素。这考虑了汉诺塔递归算法的所有可能边界情况，因为这是最简单的情景，即只有一个盘子需要移动，不需要进一步递归。这样确保了算法的正确终止和功能完整性。