#牛客堂#面试笔试题&面试笔试技巧（2015.7.15）

【嘉宾介绍】

 汉诺塔问题
A.【题目】
给定一个整数n，代表汉诺塔游戏中从小到大放置的n个圆盘，假设开始时所有圆盘都放在左边的柱子上，想按照汉诺塔游戏的要求把所有圆盘都移到右边的柱子上。实现函数打印最优移动轨迹。
【举例】
n=1时，打印：
move from left to right
n=2时，打印：
move from left to mid
move from left to right
move from mid to right

B.【进阶题目】
给定一个整型数组arr其中只含有1、2和3，代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，arr[i]的值代表第i+1个圆盘的位置。比如，arr=[3,3,2,1]，代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨迹中的第几个状态。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则返回-1。
【举例】
arr=[1,1]。两个圆盘目前都在左柱上，也就是初始状态，所以返回0。
arr=[2,1]。第一个圆盘在中柱上、第二个圆盘在左柱上，这个状态是2个圆盘的汉诺塔游戏中，最优移动轨迹的第1步，所以返回1。
arr=[3,3]。第一个圆盘在右柱上、第二个圆盘在右柱上，这个状态是2个圆盘的汉诺塔游戏中，最优移动轨迹的第3步，所以返回3。
arr=[2,2]。第一个圆盘在中柱上、第二个圆盘在中柱上，这个状态是2个圆盘的汉诺塔游戏中，最优移动轨迹从来不会出现的状态，所以返回-1。
【进阶题目要求】
如果arr长度为N，请实现时间复杂度O(N)，额外空间复杂度O(1)的方法。