Leetcode 【950、969】

2019-06-12  本文已影响0人  牛奶芝麻
题目描述:【Array】950. Reveal Cards In Increasing Order
解题思路:

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

其他过程也是如此。我们可以很容易写出代码。时间复杂度 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
上一篇下一篇

猜你喜欢

热点阅读