Leetcode 【950、969】
Leetcode 【950、969】
echobingo
发布于 2019-06-15 18:25:13
发布于 2019-06-15 18:25:13
题目描述：【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本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.06.12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录