题解 | 汉诺塔问题

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    def getSolution(self , n: int) -> List[str]:
        # write code here
        # 思路梳理：
        # 要把圆盘全部移到最右边分为三步
        # 第一步：将n-1个盘子借助右柱子移到中间
        # 第二步：将第n个盘子从左柱子移到右柱子
        # 第三步：将n-1个盘子借助左柱子移到右边
        self.result_list = []
        self.hanoi(n,'left','right','mid')
        return self.result_list
    def hanoi(self,k,source,target,auxiliary):
        if k == 1:
            self.result_list.append(f'move from {source} to {target}')
            return
        self.hanoi(k-1,source,auxiliary,target)
        self.result_list.append(f'move from {source} to {target}')
        self.hanoi(k-1,auxiliary,target,source)