LeetCode第969题 煎饼排序

题目

给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。

一次煎饼翻转的执行过程如下：

选择一个整数 k ，1 <= k <= arr.length

反转子数组 arr[0…k-1]（下标从 0 开始）

例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。

以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/pancake-sorting

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案

方法一

class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> pancakeSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int index = get(arr, i);
//            LogUtils.info("i = {}, index = {}", i, index);
            if (index == 0) {
                flip(arr, i - 1);
                flip(arr, i);
            } else if(index != i){
                flip(arr, i);
                flip(arr, i - index);
                flip(arr, i - index - 1);
                flip(arr, i);
            }
        }
        return result;
    }

    /**
     * 返回指定数会出现的位置
     * @param arr
     * @param end
     * @return
     */
    public int get(int[] arr, int end){
        int left = 0;
        int right = end - 1;

        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(arr[mid] > arr[end]){
                right = mid - 1;
            } else if(arr[mid] < arr[end]){
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    /**
     * 翻转0~n数组的数值
     * @param arr
     * @param end
     */
    public void flip(int [] arr, int end){
        if(end < 1){
            return;
        }
        result.add(end + 1);
        int left = 0;
        int right = end;
        while(left < right){
            int mid = arr[left];
            arr[left] = arr[right];
            arr[right] = mid;
            left++;
            right--;
        }
//        LogUtils.info("end = {}, arr = {}", end, (Object) arr);
    }
}

答案解析.将数组分为两个部分,数组左侧为长度为i+1的递增数组,右侧无序数组,每次从右侧无序数组中取出第一个数,并获得该数应当插入到左侧数组的位置index,对index进行判断:

• 当index == 0时,执行两次翻转,翻转数组
  
0~i-1

  的数组,然后翻转
  
0~i

  之间的数组
• 当index == i时,不执行操作
• 当index != 0 && index != 0 时,翻转(
  
0~i

  ),(
  
0~i-index

  ),(
  
0~i-index-1

  ),(
  
0~i

  )