煎饼排序

煎饼排序

969.煎饼排序

class Solution {
public:
    vector<int> res;
    vector<int> pancakeSort(vector<int>& arr) {
        int n=arr.size();
        cakeSort(arr, n);
        return res;
    }
    void cakeSort(vector<int>& arr, int n){
        //base case
        if(n==1) return;
        
        //寻找最大煎饼的索引
        int maxCake=0;
        int maxCakeIndex=0;
        for(int i=0;i<n;i++){
            if(arr[i]>maxCake){
                maxCakeIndex=i;
                maxCake=arr[i];
            }
        }
        //第一次翻转，将最大煎饼翻到最上面
        reverse(arr, 0, maxCakeIndex);
        //记录此次翻转
        res.push_back(maxCakeIndex+1);
        //第二次翻转，将最大煎饼翻到最下面
        reverse(arr, 0, n-1);
        //记录此次翻转
        res.push_back(n);

        //递归调用，翻转剩下的烧饼
        cakeSort(arr, n-1);
    }
    //翻转数组arr[i...j]的元素
    void reverse(vector<int>& arr, int i, int j){
        while(i<j){
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
};

type Solution struct {
    res []int
}

func (s *Solution) pancakeSort(arr []int) []int {
    n := len(arr)
    s.res = []int{}
    s.cakeSort(arr, n)
    return s.res
}

func (s *Solution) cakeSort(arr []int, n int) {
    //base case
    if n == 1 {
        return
    }
    
    //寻找最大煎饼的索引
    maxCake := 0
    maxCakeIndex := 0
    for i := 0; i < n; i++ {
        if arr[i] > maxCake {
            maxCakeIndex = i
            maxCake = arr[i]
        }
    }
    //第一次翻转，将最大煎饼翻到最上面
    s.reverse(arr, 0, maxCakeIndex)
    //记录此次翻转
    s.res = append(s.res, maxCakeIndex+1)
    //第二次翻转，将最大煎饼翻到最下面
    s.reverse(arr, 0, n-1)
    //记录此次翻转
    s.res = append(s.res, n)
    
    //递归调用，翻转剩下的烧饼
    s.cakeSort(arr, n-1)
}

//翻转数组arr[i...j]的元素
func (s *Solution) reverse(arr []int, i, j int) {
    for i < j {
        arr[i], arr[j] = arr[j], arr[i]
        i++
        j--
    }
}