有一个int数组arr其中只含有1、2和3，分别代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，arr[i]的值代表第i+1个圆盘的位置。比如，arr=[3,3,2,1]，代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨迹中的第几个状态。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则返回-1。
给定一个int数组arr及数组的大小n，含义如题所述，请返回一个int，代表所求的结果。
[3,3]
返回：3
package go.jacob.day1216;
import org.junit.Test;
public class Demo2 {
@Test
public void test() {
int[] arr = { 2, 1, 1, 1, 3, 2, 2, 3 };
System.out.println(chkStep(arr, arr.length));
}
public int chkStep(int[] arr, int n) {
if (arr == null || arr.length == 0 || arr.length != n)
return -1;
return process(arr, n-1, 1, 2, 3);
}
private int process(int[] arr, int i, int from, int mid, int to) {
if (i == -1)
return 0;
if (arr[i] == mid)
return -1;
if (arr[i] == from)// 说明当前轮次的最大环还在最左边的柱子上
return process(arr, i - 1, from, to, mid);
else {// 在最右柱子上
int tmp = process(arr, i - 1, mid, from, to);
if (tmp == -1)
return -1;
return (1 << i) + tmp;
}
}
}
# -*- coding:utf-8 -*-
class Hanoi:
def chkStep(self, arr, n):
# write code here
if len(arr)!=n:return
self.cur_status = [1]*n #初始状态，所有的圆盘都在左柱上
self.moves = []#记录所有的cur_status
self.moves.append(self.cur_status[:])
self.solve(n,1,2,3)
i = 0
for status in self.moves:
if arr==status:
return i
i += 1
return -1
def move(self,n,s1,s2):
self.cur_status[n-1] = s2
#print self.cur_status
self.moves.append(self.cur_status[:])
def solve(self,n,s1,s2,s3):
if n==1:
self.move(n,s1,s3)
else:
self.solve(n-1,s1,s3,s2)
self.move(n,s1,s3)#
self.solve(n-1,s2,s1,s3)
int chkState(vector<int> &state,vector<int> &arr)
{
for(int i=0; i< state.size(); i++){
if(state[i] != arr[i])
return -1;
}
return 1;
}
/*
使用原始汉诺塔递归程序，在移动盘子的过程中对每个状态进行判断，
如果和所求状态相同则返回。
*/
int hanoi(int &count,vector<int> &state,vector<int> &arr,int n,
int A,int B,int C)
{
if(n == 1){
if(chkState(state,arr) != 1){
state[n-1] = C;
count ++;
}else{
return 1;
}
}else{
if(chkState(state,arr) != 1){
hanoi(count,state,arr,n-1,A,C,B);
}else{
return 1;
}
if(chkState(state,arr) != 1){
state[n-1] = C;
count ++;
}else{
return 1;
}
if(chkState(state,arr) != 1){
hanoi(count,state,arr,n-1,B,A,C);
}else{
return 1;
}
}
return 1;
}
int chkStep(vector<int> arr, int n) {
vector<int> state(n,1);
int count = 0;
hanoi(count,state,arr,n,1,2,3);
return count;
}
import java.util.*;
public class Hanoi {
Set<Integer> left=new HashSet<Integer>();
Set<Integer> mid=new HashSet<Integer>();
Set<Integer> right=new HashSet<Integer>();
int isFind=0;
int times=0;
public int chkStep(int[] arr, int n) {
// write code here
if(n==1&&arr[0]==1)
return 0;
if(n==1&&(arr[0]==2||arr[0]==3))
return 1;
int count=n;
while(count>0)
left.add(count--);
helper(n,1,3,2,arr);
return isFind;
}
private void helper(int n,int from,int to,int depend,int[] arr){
if(n==1){
move(1,from,to,arr);
}else{
helper(n-1,from,depend,to,arr);
move(n,from,to,arr);
helper(n-1,depend,to,from,arr);
}
}
private void move(int idx,int from,int to,int[] arr){
if(from==1)
left.remove(idx);
else if(from==2)
mid.remove(idx);
else if(from==3)
right.remove(idx);
if(to==1)
left.add(idx);
else if(to==2)
mid.add(idx);
else if(to==3)
right.add(idx);
int i;
for(i=0;i<arr.length;i++){
if(arr[i]==1 && !left.contains(i+1))
break;
else if(arr[i]==2 && !mid.contains(i+1))
break;
else if(arr[i]==3 && !right.contains(i+1))
break;
}
times++;
if(i==arr.length)
isFind=times;
}
} 
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;
}
};
/*
* 开始想了没有思路，参考大神的解题思路（原来是《程序员面试指南》中的一道题目）：https://www.nowcoder.com/questionTerminal/b2d552cd60b7415fad2612a32e799812
*
* 数组下标代表盘子的大小，可以从最大的盘子（也就是数组中最后面一个元素）往前递归考虑；
*
* 1.如果当前盘子在中间，不是最优解（直观观察）；
* 2.如果当前盘子在最右边，说明数组已经完成了Hanoi的前两步，第一步将前n-1移动到中间步数为2^(n-1)-1,然后最后一个n移动到右边步数为1，总共为2^(n-1);
* 此时只需要递归判断前n-1个数组的移动次数，并且添加进来；
* 3.如果当前盘子最左边，说明对第n盘子没有进行任何操作（如果是最优解），只需要递归求解前n-1个盘子的操作次数
* 具体参见实现代码
*
* */
public class HanoiIII {
public int chkStep(int[] arr, int n) {
if (arr == null || arr.length < 1 || arr.length != n) {
return -1;
}
return checkstep(arr, n - 1, 1, 2, 3);
}
private int checkstep(int[] arr, int cur, int left, int mid, int right) {
// 所有盘子递归完毕
if (cur == -1) {
return 0;
}
// 在中间
if (arr[cur] == mid) {
// 在左边
return -1;
} else if (arr[cur] == left) {
return checkstep(arr, cur - 1, left,right,mid);
// 在右边
} else {
int tmp = checkstep(arr, cur - 1, mid,left,right);
// 如果cur-1个盘子不是最优解
if (tmp == -1) {
return -1;
}
return (1 << cur) + tmp;
}
}
}
class Hanoi {
private:
void totalStep(int n, vector<int> &ret)
{
if (n == 1) {
ret.push_back(1);
return;
}
totalStep(n - 1, ret);
ret.push_back(1 + 2 * ret.back());
}
int findStepOfBottom(const vector<int> &ref, vector<int> &arr, int cur, int src, int mid, int dst) {
if(cur == 0) {// 当前只剩最后一个盘子（exit）
if(arr[cur] == src) return 0;
if(arr[cur] == dst) return 1;
return -1;
}
if(arr[cur] == src) {
return findStepOfBottom(ref, arr, cur-1, src, dst, mid); // 比当前小1的盘子，从左边移到中间过程中，变成当前状态
} else if (arr[cur] == dst) {
int tmp2 = findStepOfBottom(ref, arr, cur - 1, mid, src, dst);
return ref[cur - 1] + tmp2 + 1; // 比当前小1的盘子，从左边移到中间 + 从中间移到当前状态 + 当前盘子，从左边移到右边
}
return -1;
}
public:
int chkStep(vector<int> arr, int n) {
// write code here
vector<int> ref;
totalStep(n, ref);
return findStepOfBottom(ref, arr, n-1, 1, 2, 3);
}
};
import java.util.*;
/**主要思想，汉诺塔的移动函数为f(n)，从left，借助mid移动到right需要几步，递归可知，f(n)=2f(n)+1,简单点儿，可以利用位运算移位来完成
*即f(n)=1<<n-1;
*1.在移动的时候对于f(n)来说，进行完f(n-1)的辅助之后，是直接把n放到目标上的，所以不会出现n在mid上的情况。
*2.所以从大到小对圆盘进行考察，若是它在left上，则是正在进行f(n-1)的操作，即正在借助right转移到mid上。还未全部完成，不需要计算。（其部分完成的交给递归来计算）
*3.若是n已经在right上了,说明已经完成了目标，当前正在进行借助left从mid到right的操作，则将其结果加起来就是答案
*/
public class Hanoi {
public int chkStep(int[] arr, int n) {
return find(arr,n-1,1,2,3);
}
public int find(int[] arr,int i,int left,int mid,int right){
//0.一般情况
if(i==-1) return 0;
//1.不可能在mid上出现n
if(arr[i]==mid) return -1;
//2.递归
if(arr[i]==left){
return find(arr,i-1,left,right,mid);
}
int res=find(arr,i-1,mid,left,right);
if(res==-1) return -1;
return res+(1<<i);
}
}
汉诺塔问题。要点在于保存好每一步的状态，最后遍历即可。。。# -*- coding:utf-8 -*-class Hanoi: def chkStep(self, arr, n): # write code here def move(a,x,y,z,l): if a == 1: state[l[0]-1] = z s.append(list(state)) return else: t = l[:len(l)-1] move(a-1,x,z,y,t) state[l[-1]-1] = z s.append(list(state)) move(a-1,y,x,z,t) l = [(i+1) for i in range(n)] state = [1 for i in range(n)] s = [list(state)] move(n,1,2,3,l) for i in range(len(s)): if s[i]==arr: return i return -1
import java.util.*;
public class Hanoi {
int step = 0;
public int chkStep(int[] arr, int n) {
if (n <= 0) return -1;
if (arr.length != n) return -1; // 不等
if (arr[n - 1] == 2) return -1; // 最大盘子不可能在中间柱子
return moveStep(arr, n, 1, 2, 3);
}
public int moveStep(int[] arr, int n, int a, int b, int c) {
if (n == 1) {
if (arr[n - 1] == a) return 0; // 在第一根柱子
if (arr[n - 1] == c) return 1; // 在第三根柱子
return -1; // 在第二根柱子不符合最优解
} else {
if (arr[n - 1] == a) {
return moveStep(arr, (n - 1), a, c, b);
} else if (arr[n - 1] == b) {
return -1;
} else if (arr[n - 1] == c) {
int tmp = moveStep(arr, (n - 1), b, a, c);
if (tmp == -1) return -1;
return (int)Math.pow(2, (n - 1)) + tmp;
}
}
return -1;
}
} 
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//这是一个不断缩小的子问题，考虑1到n-1时，说明第n个圆盘已经放好了
class Hanoi
{
private:
int chk(const vector<int>& arr, int k, const int from, const int pass, const int to)
{
if(1==k)
{
if(from==arr[k-1])return 0; //只有一个圆盘且在from上那么就在最初状态
if(to == arr[k-1])return 1; //只有一个圆盘且在to上那么就在最终状态(只有一个圆盘只需一步)
return -1;
}
if(arr[k-1] == pass) //最大那个圆盘是不可能经过辅助塔的
{
return -1;
}
//当前最大的为第k个盘，初始位置位于当前的from上，
//若所给状态其也在from上，那么说明其没有移动过，不必考虑他，直接考虑子集1到k-1
if(arr[k-1] == from)
{
return chk(arr, k-1, from, to, pass);
}
//当前最大的为第k个盘，初始位置本应在from上但给出的状态是在to上，说明其发生了移动，我们把移动分为两部分，
//一部分是把1到k-1移到pass上，第k个移到to上，第二部分为后续移动到达给定状态，
//其中第一部分需要 1<<(k-1)步，第二部分是在从pass经from到to时形成的一个过程
if(arr[k-1]==to)
{
int tmp = chk(arr, k-1, pass, from, to);
if(-1==tmp)
{
return -1;
}
return (1 << k-1)+tmp;
}
}
public:
int chkStep(vector<int> arr, int n)
{
if(n<=0)return -1;
if(arr.size()!=n)return -1;
if(arr[n-1]==2)return -1; //n-1也即最大的那个盘不可能会在第二个塔位上(最优路径下)
return chk(arr, n, 1, 2, 3);
}
};
int main()
{
vector<int> arr;
arr.push_back(3);
arr.push_back(3);
Hanoi h;
cout << h.chkStep(arr, 2) << endl;
system("pause");
return 0;
}
class Hanoi {
public:
int chkStep(vector<int> arr, int n) {
// write code here
vector<int> stat(n, 1);
if (n <= 0) return -1;
if (check(arr, stat)) return 0;
int s = 0;
return hanoi(arr, stat, n, 1, 2, 3, n-1, s);
}
int hanoi(vector<int> &arr, vector<int> &stat,
int n, int from, int depend, int to, int no, int &s) {
if (1 == n) {
stat[no] = to;
++s;
if (check(arr, stat)) return s;
return -1;
}
else {
int ret1 = hanoi(arr, stat, n-1, from, to, depend, no-1, s);
if (-1 != ret1) return ret1;
stat[no] = to;
++s;
if (check(arr, stat)) return s;
int ret2 = hanoi(arr, stat, n-1, depend, from, to, no-1, s);
return ret2;
}
}
bool check(vector<int> &arr, vector<int> &target) {
int len = arr.size();
for (int i = 0; i < len; ++i) {
if (arr[i] != target[i]) return false;
}
return true;
}
};
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
class Hanoi { private: int chk(vector<int>& arr, int k, const int from, const int pass, const int to){ if (k == 1){ if (from == arr[k - 1]) return 0; if (to == arr[k - 1]) return 1; return -1; } if (arr[k - 1] == pass){ return -1; } if (arr[k - 1] == from){ return chk(arr, k - 1, from, to, pass); } if (arr[k - 1] == to){ int tmp = chk(arr, k - 1, pass, from, to); if (tmp == -1) return -1; return (1 << k - 1) + tmp; } } public: int chkStep(vector<int> arr, int n) { // write code here if (n <= 0) return -1; if (arr.size() != n) return -1; vector<int> cur(n, 1); if (arr[n - 1] == 2) return -1; return chk(arr, n, 1, 2, 3); } };