程序员代码面试指南刷题--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;
    }
}