力扣969题(摊煎饼)

969、煎饼排序

基本思想:

找到n个煎饼中最大的那个

先把最大的烧饼放到最上面

再把这个最大的烧饼移到最底下

具体实现:

递归和循环

代码:

递归

from typing import List
class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        if len(A) == 1:
            return []

        max_val, max_pos = -1, -1
        for i, val in enumerate(A):
            if val > max_val:
                max_val, max_pos = val, i

        ans = [max_pos+1, len(A)]
        l1 = A[:max_pos+1]
        l1.reverse()
        l2 = l1 + A[max_pos+1:]
        l2.reverse()
        ans = ans +  self.pancakeSort(l2[:-1])

        return ans

循环

class Solution(object):
    def pancakeSort(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        ans =[]
        List = A
        while len(List)>2:
            maxval =max(List)
            index =List.index(maxval)
            if index:
                List=List[index::-1]+List[index+1:]
                List.reverse()
                ans.append(index+1)
                ans.append(len(List))
            else:
                ans.append(len(List))
                List.reverse()
            List.pop(-1)
        if len(List)==2 and  List[0]>List[1]:    
                ans.append(2) 
        return ans 
原文地址:https://www.cnblogs.com/zhaojiayu/p/14735861.html