编程之美 1.3：给定一个数组nums，每次只能翻转0-i之间的数字，求把nums排好序的最小翻转次数
主要思想：利用DFS遍历出所有可能结果，从中找出翻转次数最小的一种
import java.util.Arrays; //编程之美 1.3：给定一个数组nums，每次只能翻转0-i之间的数字，求把nums排好序的最小翻转次数 //主要思想：利用DFS遍历出所有可能结果，从中找出翻转次数最小的一种 public class Pancake_Sorting1 { int pancakes[];//传入的参数，要排序的数组 int swapingRecord[];//记录每个递归分支，即每种可能的翻转记录，eg.{2,1}表第一步翻转0-2之间，第二步翻转0-1之间 int swapFinalRecord[];//最终结果，翻转记录 int maxSwapTimes;//最大翻转次数，不断缩小这个值 int searchTimes;//search函数被执行的总次数 public Pancake_Sorting1(int pancakes[]){ this.pancakes = pancakes; this.maxSwapTimes = upperBound(); swapingRecord = new int[maxSwapTimes]; swapFinalRecord = new int[maxSwapTimes]; } public int upperBound() {//初始时候可以预估出的最大翻转次数 return 2*(pancakes.length-1);//暴力方法解的时候，时间复杂度O(n^2) } public int lowerBound(int array[]){//可能的最小翻转次数 if(array == null || array.length < 2) return 0; int swapTimes = 0; for (int i = 0; i < array.length-1; i++) { int diff = array[i]-array[i+1]; if(diff == -1 || diff == 1) continue; else swapTimes++; } return swapTimes; } public boolean isSorted(int array[]){//看数组是否被排好序 if(array == null) return false; for(int i = 0; i < array.length-1; i++){ if(array[i] > array[i+1]) return false; } return true; } public void reverse(int array[], int k){//翻转函数 int low = 0; int high = k; while(low < high){ int temp = array[low]; array[low] = array[high]; array[high] = temp; low++; high--; } } public void search(int step) { searchTimes++; int estimate = lowerBound(pancakes); if(step + estimate >= maxSwapTimes)//剪枝操作 return; if(isSorted(pancakes)){//如果排好序了，看看是否能更新最大翻转次数 if(step < maxSwapTimes){//能更新 maxSwapTimes = step; for (int i = 0; i < maxSwapTimes; i++) //把这个递归分支记录的翻转记录拷贝到最终结果中 swapFinalRecord[i] = swapingRecord[i]; } } else{//如果没排好序，接着递归 for (int i = 0; i < pancakes.length; i++) { reverse(pancakes, i); swapingRecord[step] = i; search(step+1); reverse(pancakes, i); } } } public void verify() {//打印并验证结果 System.out.println("搜索次数:" + searchTimes); System.out.println("翻转次数:" + maxSwapTimes); System.out.print("翻转序列:"); for (int i = 0; i < maxSwapTimes; i++) System.out.print(swapFinalRecord[i]+","); System.out.println(); System.out.println("待排序的数组是："+Arrays.toString(pancakes)); for (int i = 0; i < maxSwapTimes; i++){ reverse(pancakes, swapFinalRecord[i]); System.out.println("step" + i + ":" + Arrays.toString(pancakes)); } System.out.println("排好序的数组是：" + Arrays.toString(pancakes)); } public static void main(String[] args) { int nums[] = {4,5,1,3,2}; Pancake_Sorting1 ps = new Pancake_Sorting1(nums); ps.search(0); ps.verify(); } }参考：https://bylijinnan.iteye.com/blog/1562246
