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.

Their thinking

Pancake sorting simply means that we can only reverse the first element in the array to the KTH element in the subarray at a time and then each time we do that, we record the value.

Since each inversion is [:k](:k is the first k number inversion), we can put the maximum in order, and then do another large inversion.

  1. First, let’s store the subscript for each number
  2. It then reverses the position from the largest number in the array to zero, so that the largest number is first and then reversed to the sequential position.

code

var swap = function (i, j, arr) { [arr[i], arr[j]] = [arr[j], arr[i]]; } var reverse = function (arr, r, ind) { for (let i = 0, j = r-1; i < j; i++, j--) { swap(i, j, arr); ind[arr[i]] = i; ind[arr[j]] = j; } } var pancakeSort = function(arr) { let ind = new Array(arr.length+1), ret = []; For (let I = 0; i < arr.length; i++) ind[arr[i]] = i; for (let i = arr.length; i > 0; If (ind[I] == I - 1) continue if (ind[I] + 1! = 1) { ret.push( ind[i]+1 ); reverse(arr, ind[i] + 1, ind); } // When I does not reach the first term, invert again, and place the largest value at the end of if (I! = 1) { ret.push(i); reverse(arr, i, ind); } } return ret; };Copy the code