LeetCode刷题---969. 煎饼排序

心已赠人 2022-03-29 11:00 168阅读 0赞

## 题目要求 ##

给定数组 `A`，我们可以对其进行煎饼翻转：我们选择一些正整数 `k <= A.length`，然后反转 `A` 的前 `k` 个元素的顺序。我们要执行零次或多次煎饼翻转（按顺序一次接一次地进行）以完成对数组 `A` 的排序。

返回能使 `A` 排序的煎饼翻转操作所对应的 `k` 值序列。任何将数组排序且翻转次数在 `10 * A.length` 范围内的有效答案都将被判断为正确。

### 示例 1： ###

输入：\[3,2,4,1\]  
输出：\[4,2,4,3\]

**解释：**

我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。  
初始状态 A = \[3, 2, 4, 1\]

1.  第一次翻转后 (k=4): A = \[1, 4, 2, 3\]
2.  第二次翻转后 (k=2): A = \[4, 1, 2, 3\]
3.  第三次翻转后 (k=4): A = \[3, 2, 1, 4\]
4.  第四次翻转后 (k=3): A = \[1, 2, 3, 4\]，此时已完成排序。

### 示例 2： ###

输入：\[1,2,3\]  
输出：\[\]

**解释：**

输入已经排序，因此不需要翻转任何内容。  
请注意，其他可能的答案，如\[3，3\]，也将被接受。

### 提示： ###

1 <= A.length <= 100  
A\[i\] 是 \[1, 2, …, A.length\] 的排列

## 解题思路： ##

首先将第一个元素到最大的元素进行反转，然后将整个序列反转，然后将第一个元素的最小的元素进行反转，递归的重复上述过程，每一次递归的排序列表比上一次少一位，当列表长度为1时，结束。

### 代码实现： ###

class Solution:
        def pancakeSort(self, A):
            """ :type A: List[int] :rtype: List[int] """
            def recursion(A, maxIndex):
                if len(A) == 1:
                    return []
                A[:maxIndex+1] = A[maxIndex::-1]
                A[:] = A[::-1]
                minIndex = A.index(min(A))
                A[:minIndex+1] = A[minIndex::-1]
                return [maxIndex+1, len(A) ,minIndex+1] + recursion(A[:-1], A.index(max(A[:-1]))) 
            b = recursion(A, A.index(max(A)))
            return b

**PS.** 该算法不是最优算法，有更好算法的小伙伴欢迎在下方评论告诉我。

## 关注我 ##

既然都看到这里了，那就关注一下我的微信公众号「大学IT圈」吧~  
![在这里插入图片描述][20190108142539499.jpg]  
**干货多多，好玩多多！**

[20190108142539499.jpg]: /images/20220329/6199d0adccb1463187975842683021bc.png