问题描述

我们有由底至上为从大到小放置的 n 个圆盘，和三个柱子（分别为左/中/右即left/mid/right），开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，要求一次只能移动一个圆盘，而且大的圆盘不可以放到小的上面。

请实现一个函数打印最优移动轨迹。

给定一个 int n ，表示有 n 个圆盘。请返回一个 string 数组，其中的元素依次为每次移动的描述。描述格式为： move from [left/mid/right] to [left/mid/right]。

数据范围：1<= n <=16
要求：时间复杂度 O(3ⁿ)， 空间复杂度 O(3ⁿ)

事例1

输入：
2
返回值：
["move from left to mid","move from left to right","move from mid to right"]

解题思路

把n个盘子从left借助mid，转移到right分为三步：

• 将前n-1个盘子从left借助right,转移到mid
• 将第n个盘子从legft直接移到right
• 将前n个盘子从mid借助left移到right

class Solution:
    def getSolution(self , n: int) -> List[str]:
        # write code here
        # 新建一个空列表
        self.str1=[]
        #使用函数处理汉诺塔
        self.hannoi(n,'left','mid','right')
        return self.str1
    def hannoi(self,n,a,b,c):
        #当只有一个盘子时，只需要从left移动到right即可
        if n==1:
            self.str1.append('move from %s to %s' %(a,c))
        else:
            #将前n-1个盘子从left通过right，移动到mid
            self.hannoi(n-1,a,c,b)
            #移动第n个盘子，并把输出的字符串加入到列表中
            str2='move from %s to %s' %(a,c)
            self.str1.append(str2)
            #将前N-1个盘子从mid通过left移动到right
            self.hannoi(n-1,b,a,c)
        return self.str1