題目： LeetCode - 969. Pancake Sorting

題目說明

利用煎餅排序將一個陣列排序好。並回傳每次翻轉的個數。

解題思路

由於前面翻轉並不會影響到後面的排序，所以主要想法為每次將最大的排序到後面，接著都只翻轉前面，最後即可完成排序。使用 find() 找到當前要找的值的位置，接著翻轉一次，此時最大的值會在陣列的最前面，接著翻轉一次將這個值翻轉到後面即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vector<int>v;
        for(int i = A.size(); i > 0; --i)
        {
            int pos = find(A.begin(), A.end(), i) - A.begin();
            reverse(A.begin(), A.begin() + pos + 1);
            if(pos) v.emplace_back(pos + 1);
            reverse(A.begin(), A.begin() + i);
            v.emplace_back(i);
        }
        return v;
    }
};