C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-09-04

class Hanoi {
public:

int chkStep(vector<int> arr, int n) 
    {
        int sum = 0,st = 1,by = 2,ta = 3,i = arr.size()-1;
    	for(;i>=0&&arr[i]!=by;i--){
            if(arr[i] == ta){
                sum+=1<<i;
                swap(st,by);
            }else{
                swap(by,ta);
            }
        }
    	return i>=0?-1:sum;
    }
//注意到题中认为标号大的块就是体积更大的块，则从最大的块或最大标号处开始。
//如果最大的块还在start处，则计算子问题，如果放在了target处，则前面的一个子问题已经完成，2^n-1,再加上当前块本身的一次移动，然后再加上子问题的需要步数。
};

C++ 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2021-03-22

class Hanoi {
public:
    int chkStep(vector<int> arr, int n) {

 int sum=0,cur=arr.size()-1,start=1,target=3,bypass=2;
        for(;cur>=0&&arr[cur]!=bypass;cur--)
            if(arr[cur]==start)
               swap(bypass,target);
            else
               sum+=1<<cur,swap(bypass,start);
        return cur>=0?-1:sum;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-08-17

class Hanoi {  
public:  
    int process(vector<int> &arr,int i,int from,int mid,int to){  
        if(i==-1)  
            return 0;  
        if(arr[i]!=from && arr[i]!=to)  
            return -1;  
        if(arr[i]==from)  
            return process(arr,i-1,from,to,mid);  
        else{  
            int res=process(arr,i-1,mid,from,to);  
            if(res==-1)  
                return -1;  
            return (1<<i)+res;  
        }  
    }  
    int chkStep(vector<int> arr, int n) {  
        // write code here  
        if(arr.empty()||n<=0)  
            return -1;  
        return process(arr,n-1,1,2,3);  
    }  
};  

C++ 解法, 执行用时: 2ms, 内存消耗: 412KB, 提交时间: 2022-04-20

class Hanoi {
public:
    //第i个盘是当前最大的盘，按照最优移动应该被移动到3上去。
    int hanoi(vector<int> arr,int i,int from,int mid,int to){
        if(i==-1) return 0;
        //最大盘不会在中间
        if(arr[i] == mid) return -1;
        //最大盘还在左边，就将左的i-1个移动到中间，，，
        else if(arr[i] == from) return hanoi(arr,i-1,from,to,mid);
        //最大盘在右边
        else{
            int h = hanoi(arr,i-1,mid,from,to);
            if(h==-1) return -1;
            return (1<<i)+h;
        }
    }
    int chkStep(vector<int> arr, int n) {
        if(arr.size()==0||arr.size()!=n) return -1;
        return hanoi(arr, n-1,1,2,3);
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 416KB, 提交时间: 2022-02-27

class Hanoi {
public:
    int chkStep(vector<int> arr, int n) {
        // write code here
        if(n==0) return -1;
        int i=n-1,ans=0;
        int left=1,mid=2,right=3,temp=2;
        while(i>=0){
            if(arr[i]!=left&&arr[i]!=right){
                return -1;
            }
            else if(arr[i]==left){
                temp=right;
                right=mid;
            }
            else{
                ans+=1<<i;
                temp=left;
                left=mid;
            }
            i--;
            mid=temp;
        }
        return ans;
    }
};