Pancakes sorting

LeetCode portal 969

The title

Given an integer array arr, sort the array using pancake flipping.

The execution of a pancake flip is as follows:

Select an integer k,1 <= k <= arr.length inverse rotor array arr[0…k-1] (subscript starting from 0) for example, arr = [3,2,1,4], select k = 3 for a pancake flip, inverse rotor array [3,2,1], You get arr = 1,2,3,4.

Returns, as an array, the sequence of k values for pancake flipping operations that order arR. Any valid answer that sorts the array with a number of flips in the 10 * arr.length range will be judged correct.

Given an array of integers arr, sort the array by performing a series of pancake flips.

In one pancake flip we do the following steps:

Choose an integer k where 1 <= k <= arr.length. Reverse the sub-array arr[0…k-1] (0-indexed). For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.

Return an array of the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.

Example:

Input: arr = [3.2.4.1]
Output: [4.2.4.3]
Explanation: 
We perform 4 pancake flips, with k values 4.2.4, and 3.
Starting state: arr = [3.2.4.1]
After 1st flip (k = 4): arr = [1.4.2.3]
After 2nd flip (k = 2): arr = [4.1.2.3]
After 3rd flip (k = 4): arr = [3.2.1.4]
After 4th flip (k = 3): arr = [1.2.3.4], which is sorted.

Input: arr = [1.2.3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3.3], would also be accepted.

Copy the code

Constraints:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= arr.length
  • All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).

Thinking line

Their thinking

This problem requires us to use pancake flipping to complete the array sorting, how to find the pattern of sorting is the key. So let’s say len is equal to arr. Length and what I found by looking at it

  1. We can start by finding the largest numberiThen the pancake flipsk= i+1Let the largest number go first.
  2. Then we flip the pancakeslenLet’s put the largest number in the back, and thenlen --.
  3. And then we findarr[0~-2]To perform the operation1 ~ 2All the way toi=2So far.
  4. For the pancake flipping process: if our flipping number isk, let’s make a minimum subscripta=0, the implementation ofswap(arr[a],arr[k-1])To exchange data, and then executea ++,b --Can. untila>=bUntil, the pancake flipping process is considered complete.

The entire code is implemented as follows

/ * * *@param {number[]} arr
 * @return {number[]}* /
var pancakeSort = function (arr) {

    // Find the position of the largest number I, then flip the pancake I +1; Let's put the largest number first
    // Then the pancake flips arr.length so that the largest number is last
    Arr [0~-2] = arR [0~-2] = arR [0~-2] Execute until I = 1;
    // Each I = k-1 - I;
    // The code is as follows
    const res = [];
    let max = 0;
    for (let i = arr.length; i > 1; i--) { // Set the maximum value of the pancake after flipping
        for (let j = 0; j < i; j++) { // Iterate to find the largest value
            if (arr[j] > arr[max]) {
                max = j;
            }
        }
        pancake(arr, max+1); // Do the pancake flip on the maximum value
        pancake(arr,i); // Store the maximum value at the end of this sort
        res.push(max+1) // Store the k value of the pancake sort
        res.push(i)

        max = 0
    }
    return res;
};
function pancake(arr,b) {
    let a = 0;
    while(a < b-1) {
        [arr[a], arr[b-1]] = [arr[b-1], arr[a]]; a++; b--; }}Copy the code

This is my solution to this question. If you have any questions or better solutions, please leave a comment and interact.