Leetcode 【950、969】

题目描述：【Array】950. Reveal Cards In Increasing Order

解题思路：

这道题有些脑筋急转弯。正着看过程没有思路，但是倒着看可以发现规律：比如牌组中有 [11,17,13]，现在要把 7 加进去，变成 [7,13,11,17]，可以进行如下操作：

• 把牌组尾部的 13 移到牌组的头部；
• 把要加进去的 7 放到牌组的头部。

其他过程也是如此。我们可以很容易写出代码。时间复杂度 O(n)，空间复杂度 O(n)。

Python3 实现：

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        if len(deck) == 1:
            return deck
        deck.sort(reverse=True)
        show = [deck[0]]
        for i in range(1, len(deck)):
            show.insert(0, show.pop())
            show.insert(0, deck[i])
        return show

题目描述：【Array】969. Pancake Sorting

解题思路：

因为反转的次数不超过 10 * length(A) 次，我们可以将最大的元素（在位置 i，下标从 1 开始）进行煎饼翻转 i 操作将它移动到序列的最前面，然后再使用煎饼翻转 A.length 操作将它移动到序列的最后面。 此时，最大的元素已经移动到正确的位置上了，所以之后我们就不需要再使用 k 值大于等于 A.length 的煎饼翻转操作了。

我们可以重复这个过程直到序列被排好序为止。 每一步，我们只需要花费两次煎饼翻转操作。

注意：因为数组 A 中的数值是 [1, 2, ..., A.length] 的一个排列，因此在编程时只需要找到最大值，然后从 max(A) 循环递减 N 次到 1 即可。每最后得到的 K 序列的长度一定是 2 * A.length。

Python3 实现：

class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        max_ = max(A)
        N = len(A)
        kseq = []
        for i in range(max_, 0, -1):
            for j in range(N):
                if i == A[j]:
                    kseq.extend([j+1, N])
                    B = A[:j+1]
                    B.reverse()  # 第一次翻转
                    A = B + A[j+1:N]
                    A.reverse()  # 第二次翻转
                    N -= 1
                    break
        return kseq