编程之美 烙饼问题 java实现（检测状态是否出现过）

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Set;

 

/**

 * 对应编程之美的烙饼翻转

 * @author sunlujing

 *

 */

public class CookieReverse {

 

private int cookie_cnt =10;

private int[] cookies={3,2,1,6,5,4,9,8,7,0};

private int [] med_cookies_states= {3,2,1,6,5,4,9,8,7,0};

private int max_step = 2*(cookie_cnt);

private int[] switchStrategy = new int[max_step];

private int[] switchStrategy_res = new int[max_step];

private Map<String,Integer> searchStates = new HashMap<String,Integer>();

 

public int lowerbound(int [] med_cookies_states){

int res=0;

for(int i=1;i< cookie_cnt;i++){

if(Math.abs(med_cookies_states[i]-med_cookies_states[i-1])!=1){

res++;

}

}

return res;

}

 

/**

* 记录状态是否搜索过

* 使用hashMap来作为state的key值，value 为该状态下所经历的step

* 如果当前状态的step值比hashmap中的小，则不需要剪掉这个分支

* @param med_cookies_states

* @param step

* @return

*/

public boolean isUnSearch(int [] med_cookies_states,int step){

String temp="";

for(int i=0;i< cookie_cnt;i++){

temp+=String.valueOf(med_cookies_states[i]);

}

if(searchStates.get(temp)==null){

searchStates.put(temp, step);

return true;

}else{

if(searchStates.get(temp) >step){

searchStates.put(temp, step);

return true;

}else{

return false;

}

}

}

 

public boolean isSorted(int [] med_cookies_states){

for(int i=1;i< cookie_cnt;i++){

if(med_cookies_states[i-1] > med_cookies_states[i]){

return false;

}

}

return true;

}

 

public void reverse(int begin,int end){

int i,j,t;

for(i=begin,j=end;i<j;i++,j--){

 

t = med_cookies_states[i];

med_cookies_states[i] = med_cookies_states[j];

med_cookies_states[j] =t ;

 

}

 

}

 

public void showStrategy(){

for(int i=0;i<max_step;i++){

System.out.print(switchStrategy_res[i]+" ");

}

}

 

public void search(int step){

int lowerBound = lowerbound(med_cookies_states);

if(lowerBound+step >= max_step){

return ;

}

if(!isUnSearch(med_cookies_states,step)){return;}

if(isSorted(med_cookies_states)){

if(step < max_step){

max_step = step;

for(int i=0;i<max_step;i++){

switchStrategy_res[i]=switchStrategy[i];

}

}

return;

}

 

for(int i=1; i < cookie_cnt;i++){

reverse(0,i);

switchStrategy[step]=i;

search(step+1);

reverse(0,i);

}

 

}

 

public static void main(String[] args) {

CookieReverse ins = new CookieReverse();

ins.search(0);

System.out.println(ins.max_step);

ins.showStrategy();

}

}