[LeetCode] 969. Pancake Sorting

[grandyang]

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[1...k].

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  thek-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.
Notice that we return an array of the chosen k values of the pancake flips.

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).

这道题给了长度为n的数组，由1到n的组成，顺序是打乱的。现在说我们可以任意翻转前k个数字，k的范围是1到n，问怎么个翻转法能将数组翻成有序的。题目说并不限定具体的翻法，只要在 10*n 的次数内翻成有序的都是可以的，任你随意翻，就算有无效的步骤也无所谓。题目中给的例子1其实挺迷惑的，因为并不知道为啥要那样翻，也没有一个固定的翻法，所以可能会误导大家。必须要自己想出一个固定的翻法，这样才能应对所有的情况。博主想出的方法是每次先将数组中最大数字找出来，然后将最大数字翻转到首位置，然后翻转整个数组，这样最大数字就跑到最后去了。然后将最后面的最大数字去掉，这样又重现一样的情况，重复同样的步骤，直到数组只剩一个数字1为止，在过程中就把每次要翻转的位置都记录到结果 res 中就可以了，注意这里 C++ 的翻转函数 reverse 的结束位置是开区间，很容易出错，参见代码如下：

解法一：

class Solution {
public:
    vector<int> pancakeSort(vector<int>& arr) {
        vector<int> res;
        while (arr.size() > 1) {
            int n = arr.size(), i = 0;
            for (; i < n; ++i) {
                if (arr[i] == n) break;
            }
            res.push_back(i + 1);
            reverse(arr.begin(), arr.begin() + i + 1);
            res.push_back(n);
            reverse(arr.begin(), arr.end());
            arr.pop_back();
        }
        return res;
    }
};

上论坛看了一下，发现高分解法都是用类似的思路，看来英雄所见略同啊，哈哈～ 不过博主上面的方法可以略微优化一下，并不用真的从数组中移除数字，只要确定个范围就行了，右边界不断的缩小，效果跟移除数字一样的，参见代码如下：

解法二：

class Solution {
public:
    vector<int> pancakeSort(vector<int>& arr) {
        vector<int> res;
        for (int i = arr.size(), j; i > 0; --i) {
            for (j = 0; arr[j] != i; ++j);
            reverse(arr.begin(), arr.begin() + j + 1);
            res.push_back(j + 1);
            reverse(arr.begin(), arr.begin() + i);
            res.push_back(i);
        }
        return res;
    }
};

Github 同步地址:

#969

参考资料：

https://leetcode.com/problems/pancake-sorting/

https://leetcode.com/problems/pancake-sorting/discuss/214213/JavaC%2B%2BPython-Straight-Forward

https://leetcode.com/problems/pancake-sorting/discuss/214200/Java-flip-the-largest-number-to-the-tail

LeetCode All in One 题目讲解汇总(持续更新中...)