969. Pancake sorting

Address :

Power button https://leetcode-cn.com/problems/pancake-sorting/

subject ：

Give you an array of integers arr , Please use Pancake flip Finish sorting the array .

The execution process of a pancake flip is as follows ：

Choose an integer k ,1 <= k <= arr.length
Anti rotor array arr[0...k-1]（ Subscript from 0 Start ）
for example ,arr = [3,2,1,4] , choice k = 3 Make a pancake flip , Anti rotor array [3,2,1] , obtain arr = [1,2,3,4] .

Returning as an array enables arr Corresponding to the orderly pancake flipping operation k Value sequence . Any array that is sorted and flipped a few times  10 * arr.length All valid answers within the range will be judged to be correct .

Example 1：

Input ：[3,2,4,1] Output ：[4,2,4,3] explain ： We execute 4 Turn the pancake over again ,k Values, respectively 4,2,4, and 3. The initial state arr = [3, 2, 4, 1] After the first flip （k = 4）：arr = [1, 4, 2, 3] After the second flip （k = 2）：arr = [4, 1, 2, 3] After the third flip （k = 4）：arr = [3, 2, 1, 4] After the fourth flip （k = 3）：arr = [1, 2, 3, 4], Sorting is now complete .

Example 2：

Input ：[1,2,3] Output ：[] explain ： The input has been sorted , So there's no need to flip anything . Please note that , Other possible answers , Such as [3,3] , Will also be judged to be correct .

Tips ：

1 <= arr.length <= 100 1 <= arr[i] <= arr.length arr All integers in are different from each other （ namely ,arr It's from 1 To arr.length An arrangement of integers ）

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/pancake-sorting
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

First of all, we need to find a “ The formula ”, You can deduce the final result on paper before you see how to write the code

You can know the title ：

1. Array element values are not equal , It means that there is a maximum , minimum value

2. If the results are in ascending order

3. Flip yes 0~k-1, It means that if you put the minimum value first , Then the subsequent flipping is in vain

        So we need to find Maximum , Make it to the end through operation , In this way, the whole string becomes a substring

        Then repeat the action to converge to an element , Achieve ascending order

What if we put the maximum value at the end ？

Example ： 3,2,4,1

1. Find the maximum

        3,2,4,1        , Its coordinates idx = 2, The maximum coordinate of the current string  maxIdx = 3

2. Flip k = idx+1 = 3

        4,2,3,1        , The maximum value is [0]

3. Flip k = maxIdx + 1 = 4

        1,3,2,4        , The maximum value is placed at the end , At this time, we need to reduce the range of strings  maxIdx  = 2

So circular , The resulting 1,2,3,4

The optimization part is , If the maximum coordinate found is just at the end , Then directly reduce the string range , No flipping is required

Method 1 、 Cycle the maximum value to the end

void dispArr(int *arr, int arrSize)
{
    printf("arr = [");
    for(int i=0; i<arrSize; i++)
        printf("%d ", arr[i]);
    printf("]\n\n");
}

int findMaxnumIdx(int *arr, int lastIdx)
{
    int max = arr[0];
    int maxIdx = 0;

    for(int i=0; i<=lastIdx; i++)
    {
        if(max < arr[i])
        {
            maxIdx = i;
            max = arr[i];
        }
    }

    return maxIdx;
}

void reversArr(int *arr, int lastIdx)
{
    int l = 0, r = lastIdx;
    while(l < r)
    {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;

        l++;
        r--;
    }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* pancakeSort(int* arr, int arrSize, int* returnSize){
    int i = 0;
    int k, cnt = 0;
    int rlen = arrSize * 2;
    int *ret = (int *)malloc(sizeof(int) * rlen);
    
    int maxIdx = arrSize - 1;

    while(maxIdx != 0)
    {
        int idx = findMaxnumIdx(arr, maxIdx);
        //printf("idx=%d, maxIdx=%d\n", idx, maxIdx);
        if(idx == maxIdx)
        {
            maxIdx--;
            rlen--;
            continue;
        }
    
        //dispArr(arr, arrSize);
        reversArr(arr, idx);
        //dispArr(arr, arrSize);
        reversArr(arr, maxIdx);
        //dispArr(arr, arrSize);
        k = idx + 1;
        //printf("k=%d\n\n", k);
        ret[i++] = k;
        k = maxIdx + 1;
        //printf("k=%d\n\n", k);
        ret[i++] = k;

        cnt+=2;

        maxIdx--;
    }

    if(rlen != cnt)
    {
        rlen = cnt;
        ret = (int *)realloc(ret, sizeof(int) * rlen);
    }

    *returnSize = rlen;
    return ret;
}

See more brush notes