## [Leetcode]969. Pancake Sorting (C++)

### 题目描述

Given an array of integers A, We need to sort the array performing a series of pancake flips.

In one pancake flip we do the following steps:

• Choose an integer k where 0 <= k < A.length.
• Reverse the sub-array A[0…k]. For example, if A = [3,2,1,4] and we performed a pancake flip choosing k = 2, we reverse the sub-array [3,2,1], so A = [1,2,3,4] after the pancake flip at k = 2.

Return an array of the k-values of the pancake flips that should be performed in order to sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

### 例子

#### 例子 1

Input: A = [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: A = [3, 2, 4, 1] After 1st flip (k = 4): A = [1, 4, 2, 3] After 2nd flip (k = 2): A = [4, 1, 2, 3] After 3rd flip (k = 4): A = [3, 2, 1, 4] After 4th flip (k = 3): A = [1, 2, 3, 4], which is sorted. Notice that we return an array of the chosen k values of the pancake flips.

#### 例子 2

Input: A = [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.

### Note

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

### 解题思路

``````#include <vector>
#include <algorithm>

class Solution {
public:
std::vector<int> pancakeSort(std::vector<int>& A) {
int n = A.size();
std::vector<int> results;
for (int target = n; target > 0; target--) {

int index;
// find current target from list
for (index = 0; index < target; index++) {
if (A[index] == target) break;
}

if (index == target - 1) continue;

// reverse [0, index] to get target to the first of list
if (index != 0) {
flip(A, index + 1);
results.push_back(index + 1);
}

// reverse [0, target - 1] to put target to correct position
if (index != target - 1){
flip(A, target);
results.push_back(target);
}

}

return results;
}

private:
// reverse the first k elements in the list
void flip(std::vector<int>& A, int k) {
std::reverse(A.begin(), A.begin() + k);
}
};
``````
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)