题目如下:

解题思路:本题没有要求求出最少的操作次数,而且规定了操作上限是 10 * A.length。我的方法是首先把最大的数移到最后,这里只需要两步,第一是找出最大的数的位置,并且把这一段反转,这样的话最大数就在第一位了,接下来逆转整个数组,最大数就被翻转到最后。接下来是次大数,方法也一样,只不过在操作的过程中不处理数组最后一个元素(即已经放好位置的最大数)。这种方法理论上的最大操作次数是 2 * A.length。

代码如下:

class Solution(object):
def pancakeSort(self, A):
"""
:type A: List[int]
:rtype: List[int]
"""
bound = len(A)
sa = sorted(A)
end = len(A)
res = []
while A != sa:
inx = A.index(bound)
if inx != 0:
A = A[0:inx+1][::-1] + A[inx+1:]
res.append(inx+1)
A = A[:end][::-1] + A[end:]
res.append(end)
end -= 1
bound -= 1
return res
05-11 19:20