本文共 2275 字，大约阅读时间需要 7 分钟。

Given an array of integers arr, sort the array by performing a series of pancake flips.

In one pancake flip we do the following steps:

• Choose an integer k where 1 <= k <= arr.length.
• Reverse the sub-array arr[0...k-1] (0-indexed).

For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.

Return an array of the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.

Example 1:

Input: arr = [3,2,4,1]Output: [4,2,4,3]Explanation: We perform 4 pancake flips, with k values 4, 2, 4, and 3.Starting state: arr = [3, 2, 4, 1]After 1st flip (k = 4): arr = [1, 4, 2, 3]After 2nd flip (k = 2): arr = [4, 1, 2, 3]After 3rd flip (k = 4): arr = [3, 2, 1, 4]After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

Example 2:

Input: arr = [1,2,3]Output: []Explanation: The input is already sorted, so there is no need to flip anything.Note that other answers, such as [3, 3], would also be accepted.

Constraints:

• 1 <= arr.length <= 100
• 1 <= arr[i] <= arr.length
• All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

题意：给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。一次煎饼翻转的执行过程如下：

• 选择一个整数 k ，1 <= k <= arr.length
• 反转子数组 arr[0...k-1]（下标从 0 开始）

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

解法 排序

类似冒泡排序的思想，每次先找到剩余数组区间中的最大数组元素，然后通过翻转将其放置在区间末尾，直到整个数组都有序为止。这一做法的翻转次数最多为 2 * arr.length ，因为对每个最大数组元素，可能需要先翻转到数组首位，然后翻转到区间尾部。

class Solution {
   public:    vector
   
     pancakeSort(vector
    
     & arr) {
           vector
     
       ans;        for (int i = arr.size() - 1; i >= 0; --i) {
               int maxj = 0;            for (int j = 1; j <= i; ++j) if (arr[j] > arr[maxj]) maxj = j;            if (maxj == i) continue; //最大值在末尾            ans.push_back(maxj + 1); //翻转arr[0,maxj]这一区间,将最大值翻转到数组首位            reverse(arr.begin(), arr.begin() + maxj + 1);            ans.push_back(i + 1); //翻转arr[0,i]这一区间,将最大值翻转到i位            reverse(arr.begin(), arr.begin() + i + 1);        }        return ans;    }};
     
    
   

运行效率如下所示：

执行用时：4 ms, 在所有 C++ 提交中击败了78.95% 的用户内存消耗：10.8 MB, 在所有 C++ 提交中击败了76.12% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/117639980 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！