題目

給你一個整數數組 arr ，請使用 煎餅翻轉 完成對數組的排序。
一次煎餅翻轉的執行過程如下：
選擇一個整數 k ，1 <= k <= arr.length
反轉子數組 arr[0…k-1]（下標從 0 開始）
例如，arr = [3,2,1,4] ，選擇 k = 3 進行一次煎餅翻轉，反轉子數組 [3,2,1] ，得到 arr = [1,2,3,4] 。
以數組形式返回能使 arr 有序的煎餅翻轉操作所對應的 k 值序列。任何將數組排序且翻轉次數在 10 * arr.length 范圍內的有效答案都將被判斷為正確。
示例 1：
輸入：[3,2,4,1]
輸出：[4,2,4,3]
解釋：
我們執行 4 次煎餅翻轉，k 值分別為 4，2，4，和 3。
初始狀態 arr = [3, 2, 4, 1]
第一次翻轉后（k = 4）：arr = [1, 4, 2, 3]
第二次翻轉后（k = 2）：arr = [4, 1, 2, 3]
第三次翻轉后（k = 4）：arr = [3, 2, 1, 4]
第四次翻轉后（k = 3）：arr = [1, 2, 3, 4]，此時已完成排序。
示例 2：
輸入：[1,2,3]
輸出：[]
解釋：
輸入已經排序，因此不需要翻轉任何內容。
請注意，其他可能的答案，如 [3，3] ，也將被判斷為正確。
提示：
1 <= arr.length <= 100
1 <= arr[i] <= arr.length
arr 中的所有整數互不相同（即，arr 是從 1 到 arr.length 整數的一個排列）
來源：力扣（LeetCode）

解題思路

??這個題有點魔方還原的味道，都是有固定套路的。題目給定的操作是旋轉前面的元素，也就是如果我們一個一個元素排序的話，先排好的一定是在尾巴，因為前面的元素要頻繁變動，排序時，先將最大的元素放在頭部然后再調到尾部，一旦我們將最大的元素放在尾巴，那么我們將會得到一個短一個元素的待處理數組，這樣我們就可以以同樣的操作處理短一些的數組。

class Solution:def pancakeSort(self, arr: List[int]) -> List[int]:A=sorted(arr)  #目標def Reverse(index):  #旋轉前k個字符for i in range((index+1)//2):temp=arr[i]arr[i]=arr[index-i]arr[index-i]=temptemp=[]  #記錄旋轉的尾巴下標i=len(arr) while A!=arr: #檢查是否符合條件index=arr.index(max(arr[0:i]))  #找出最大的元素temp.append(index+1)  Reverse(index)  #先放到頭部arr[0:i]=arr[0:i][::-1]  #然后調到尾部temp.append(i)i-=1return temp

總結

以上是生活随笔為你收集整理的LeetCode中等题之煎饼排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。