Description
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
where1 <= 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 from1
toarr.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 同步地址:
参考资料:
https://leetcode.com/problems/pancake-sorting/
https://leetcode.com/problems/pancake-sorting/discuss/214213/JavaC%2B%2BPython-Straight-Forward