969. 煎饼排序（算法思维系列）

骑猪看日落 2023-10-05 20:30 5阅读 0赞

#### 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 范围内的有效答案都将被判断为正确。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

第一次找到最大的煎饼，翻到最上面，然后再翻一次，把最大的煎饼翻到底部，重复上述过程。

## 代码 ##

class Solution {
        
        List<Integer> res = new LinkedList<>();
    
        public List<Integer> pancakeSort(int[] arr) {
        
            sort(arr, arr.length);
            return res;
        }
    
        // 将前n块烧饼排序
        public void sort(int[] arr, int n) {
        
            if (n == 1) {
        
                return;
            }
    
            //寻找最大烧饼的索引
            int maxCake = 0;
            int maxCakeIndex = 0;
    
            for (int i = 0; i < n; i++) {
        
                if (arr[i] > maxCake) {
        
                    maxCake = arr[i];
                    maxCakeIndex = i;
                }
            }
            //把最大的烧饼反转到顶部
            reverse(arr, 0, maxCakeIndex);
            //记录下标。注意要比正常下标多1
            res.add(maxCakeIndex + 1);
            //再把最大烧饼反转到底部
            reverse(arr, 0, n - 1);
            res.add(n);
    
            //递归调用，翻转剩下的烧饼
            sort(arr, n - 1);
    
    
        }
    
        public void reverse(int[] arr, int i, int j) {
        
            while (i < j) {
        
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210226135733887.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70