[leetcode] 969. Pancake Sorting

[leetcode] 969. Pancake Sorting

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 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 the k-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.

Note:

1 <= arr.length <= 1001 <= arr[i] <= arr.lengthAll integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

分析

题目的意思是：给你一个数组，进行翻转，比如选择K了之后，就把第1～K个数翻转一下，直到数组有序为止。输出所选择的K. 这道题我没做出来，看了答案之后我也没看多大明白，flip是翻转操作，题目给的条件是所有的数都是唯一的，并且是一个1到数组长度的一个排列。有了这个条件我们就能知道数组中的最大值是哪个，做类似冒泡排序，首先找到最大值的位置，然后把它放到末尾，数组进行翻转，依次类推，直到所有的数都放到合适的位置为止。里面的细节我不是很懂，所以我把每次的arr翻转后的输出给打印了出来

[4, 2, 3, 1][1, 3, 2, 4][3, 1, 2, 4][2, 1, 3, 4][1, 2, 3, 4][3, 4, 2, 3, 2]

代码

class Solution: def pancakeSort(self, arr: List[int]) -> List[int]: def flip(sublist,k): i=0 while(i0): # locate the position for the value to sort in this round index=arr.index(value_to_sort) if(index!=value_to_sort-1): # flip the value to the head if necessary if(index!=0): ans.append(index+1) flip(arr,index+1) ans.append(value_to_sort) flip(arr,value_to_sort) value_to_sort-=1 return ans

参考文献

​​[LeetCode] Approach 1: Sort like Bubble-Sort​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。