Leetcode 969. Pancake Sorting

Posted on | | 阅读数
Words count in article: 185 | Reading time ≈ 1

Question

Solution

注意到，A是1-n的排列。考虑A中最大元素是不是在其应该所在的位置。如果在则选择第2大的元素。如果不在就翻转。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        n = len(A)
        output = []
        for i in list(range(n, 0, -1)):
            currentIdx = A.index(i)
            if currentIdx < i - 1:
                output.append(currentIdx + 1)
                output.append(i)
                # output += [currentIdx+1, i]
                A = A[:currentIdx+1][::-1] + A[currentIdx+1:]
                A = A[:i][::-1] + A[i:] 
        return output

不判断是不是在其位置，直接旋转。因为只要求返回K，所以在最后直接去掉A的最大元素。

1
2
3
4
5
6
7
8
9
class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        n = len(A)
        output = []
        for i in list(range(n, 0, -1)):
            currentIdx = A.index(i)
            output += [currentIdx+1, i]
            A = A[:currentIdx:-1] + A[:currentIdx]
        return output