“This is the 23rd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

What is “pancake sort”?

It’s called pancake sorting. So what is pancake flipping? (No nesting dolls 🐶)

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.

Such as:

Input: [3,2,4,1] Output: [4,2,4,3] Explanation: We perform four pancake flips with k values of 4,2,4, and 3. 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], at this point the sorting has been completed.Copy the code

Answer:

  1. Do two flips each time you find the maximum
  2. Flip it to the top for the first time
  3. Flip it to the bottom a second time

So each round will put the largest one at the bottom and repeat until you get to the first one.

JavaScript implementation:

/** * @param {number[]} arr * @return {number[]} */ var pancakeSort = function(arr) { const res = []; sort(arr, arr.length); return res; function sort(cakes, n) { if (n === 1) return; Let maxCake = 0; let maxCakeIndex = 0; for (let i = 0; i < n; i++) { if (cakes[i] > maxCake) { maxCake = cakes[i]; maxCakeIndex = i; } // Reverse (cakes, 0, maxCakeIndex) to the top; // Record reverse res.push(maxCakeIndex + 1); Reverse (cakes, 0, n-1) reverse(cakes, 0, n-1); res.push(n); // sort(cakes, n-1); Function reverse (arr, I, j) {while (I < j) {const temp = arr[I]; arr[i] = arr[j]; arr[j] = temp; i++; j--; }}};Copy the code

Validation:

OK, that’s it

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~