969. Pancake Sorting

发表于

每日一题 2019 - 01 - 24

题目：

Given an array A, we can perform a pancake flip: We choose some positive integer **k** <= A.length, then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

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

Example 1:

1
2
3
4
5
6
7
8
9
Input: [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.

Example 2:

1
2
3
4
Input: [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. 1 <= A.length <= 100
  2. A[i] is a permutation of [1, 2, ..., A.length]

解法：

这个题的意思是让我们使用pancake sort对给定数组进行排序，并且记录下每次排序的位置，关于pancake sort的排序思路是：

  • 每次找出最大的待排元素的位置 pos
  • 翻转 0 到 pos 位置的元素
  • 记录 pos + 1
  • 翻转 0 到 末尾（这里的末尾指的是待排序列的末尾，每两次翻转之后，都会有一个元素被放置在应该放置的位置）
  • 记录 末尾元素 i

返回上述的记录过程

注：

这里有个地方需要提醒一下，题目中给出的example的序列[3,2,4,1]的正确排序过程应该是[3,4,2,3,1,2]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    vector<int> pancakeSort(vector<int>& a) {
        vector<int> ret;
        if(isSorted(a))
            return ret;
        for(int i=a.size();i>0;i--)
        {
            if(isSorted(a))
                break;
            int pos=findMax(a,i);
            reverse(a.begin(),a.begin()+pos+1);
            ret.emplace_back(pos+1);
            reverse(a.begin(),a.begin()+i);
            ret.emplace_back(i);
        }
        return ret;        
    }
    int findMax(vector<int>& a, int e)//找到0到end的序列中，最大值的位置
    {
        int max=a[0];
        int pos=0;
        for(int i=1;i<e;i++)
        {
            if(a[i]>max)
            {
                max=a[i];
                pos=i;
            }
        }
        return pos;
    }
    bool isSorted(vector<int>& a)//判断当前序列是否有序
    {
        for(int i=1;i<a.size();i++)
        {
            if(a[i]<a[i-1])
            {
                return false;
            }
        }
        return true;
    }
};
0%
undefined