程式員代碼面試指南刷題--31.漢諾塔問題

題目描述

給定一個整數n，代表漢諾塔遊戲中從小到大放置n個圓盤，假設開始所有圓盤都在左邊的柱子上，那麼用最優的辦法把所有圓盤都移動到右邊的柱子上的過程，就稱為最優移動軌迹。給定一個整型數組arr, 其中隻含有1、2和3,代表所有圓盤目前的狀态，1代表左柱，2代表中柱，3代表右柱，a[i]的值代表第i+1個圓盤的位置（a[i]下标從0開始）。比如，arr=[3,3,2,1], 代表第1個圓盤在右柱上、第2個圓盤在右柱上、第3個圓盤在中柱上、第4個圓盤在左柱上。如果arr代表的狀态是最優移動軌迹過程中出現的狀态，輸出arr這種狀态是最優移動軌迹中的第幾個狀态（由于答案可能較大，請輸出對109+710^9+7109+7取模後的答案）。如果arr代表的狀态不是最優移動軌迹過程中出現的狀态，則輸出-1。

輸入描述:

輸入包括兩行，第一行一個整數n(1≤n≤2∗106)( 1 \leq n \leq 2*10^6)(1≤n≤2∗106)，表示圓盤的個數，第二行n個正整數，且均為1或2或3，第i個整數表示第i個圓盤位置。

輸出描述:

輸出一個整數，表示這種狀态是第幾個最優移動狀态（輸出對109+710^9+7109+7取模後的答案），無解輸出-1。

示例1
輸入

2
1 1

輸出

0

示例2
輸入

2
3 3

輸出

3
           

解法一：遞歸

import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        String[] ss = br.readLine().trim().split(" ");
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            arr[i] = Integer.parseInt(ss[i]);
        }
        System.out.println(step(arr));
    }
    public static int step(int[] arr){
        if(arr==null||arr.length==0) return -1;
        return process(arr,arr.length-1,1,2,3);
    }
    public static int process(int[] arr,int i,int from,int mid,int to){
        if(i==-1) return 0;
        if(arr[i] != from&&arr[i] != to){
            return -1;
        }else if(arr[i]==from){
            return process(arr,i-1,from,to,mid);
        }else{
            int rest = process(arr,i-1,mid,from,to);
            if(rest==-1){
                return -1;
            }
            return (1<<i)+rest;
        }
    }
}
           

解法二 非遞歸

import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        String[] ss = br.readLine().trim().split(" ");
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            arr[i] = Integer.parseInt(ss[i]);
        }
        System.out.println((int)getStatus(arr));
    }
    public static long getStatus(int[] arr){
        int i = arr.length - 1;
        int from = 1;
        int mid = 2;
        int to = 3;
        int tmp = 0;
        long result = 0;
        int[] count = new int[i + 1];
        count[0] = 1;
        for(int j = 1; j < i + 1;j++){
            count[j] = (int)((count[j - 1] << 1) % (1e9 + 7));
        }
        while(i >= 0){
            if(arr[i] != from && arr[i] != to){
                return -1;
            }
             
            if(arr[i] == from){
                tmp = mid;
                mid = to;
                to = tmp;
            }else{
                tmp = from;
                from = mid;
                mid = tmp;
                result += count[i];
                result %= 1000000007;
            }
             
            i--;
         
        }
        return (long)result;
    }
}