Leetcode 969 Pancake Sorting

发表于 |

给定一个数组A，现在定义一个操作”pancake flip”，这个操作是我们选择一个数字k，然后将数组A的前k个数翻转

现在，经过若干次”pancake flip”操作，使得数组A是排好序的状态（从小到大），求出这个操作次数。

Example 1:
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:
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]

思路分析：
首先我们思考一下，根据题目定义的操作，每次只会影响到数组中的前k个数。想一想标准的排序算法，比如快排，都是一次先将一些数放在他本身该在的地方。
所在这道题中，我们也按照这个思路，我们将最大的数放到最后一个位置，然后将第二大的数放到倒数第二个位置，依次类推。
然后思考，如何将最大的数放到最后呢？
我们注意到翻转前k个数会将第k个数放到第一个位置，如果此时再将整个数组翻转，那么就可以将第k个数放到最后面了。

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
class Solution(object):
    def pancakeSort(self, A):
        # 记录每个数的index，由于翻转过程中index会变动，用solve_index来处理
        d = {v:i for i,v in enumerate(A)}
        def solve_index(index):
            index -= 1
            for v,i in d.items():
                if i <= index:
                    d[v] = index - i
        # 从最大的数开始分析
        res = []
        ma = max(A)
        while ma > 1:
            index = d[ma]
            if index == ma - 1: # 就在他本来的位置上就不做处理
                ma -= 1
                continue
            res.append(index+1)
            solve_index(index + 1)
            res.append(ma)
            solve_index(ma)
            ma -= 1
        return res

# 215 / 215 test cases passed.
# diffculty: medium
# Runtime: 72 ms