[B] [C] [D]

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

The execution of a pancake flip is as follows:

  • Pick an integerk ，1 <= k <= arr.length
  • Antirotor arrayarr[0...k-1](The subscripts start at 0)

For example, arr = [3,2,1,4], select k = 3 for a pancake flip, invert the rotor array [3,2,1], and 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.

Example 1:

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

Example 2:

Input: [1,2,3] output: [] explanation: the inputs are sorted, so there is no need to flip anything. Note that other possible answers, such as [3,3], will also be judged correct.Copy the code

Tip:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= arr.length
  • arrAll integers in are different (i.e.,arrfrom1 到 arr.lengthA permutation of integers)

Because every flip starts at subscript 0

To complete the sorting, place the maximum value at the end of the unprocessed range each time

To put the maximum at the end of the range, first flip the value to subscript 0

And then flip the interval from 0 to the target position

This operation completes the operation of placing the maximum value of the interval to be processed at the end of the interval

Repeat the process from the end of the array forward. When the entire array is processed, the original array is ordered

During the processing, the subscript position +1 at the end of each turnover interval is recorded, which is the k value of this operation

The whole process is as follows:

The code is as follows:

Var pancakeSort = function(arr) {var pancakeSort = function(arr) {var pancakeSort = function(arr) { While (cur>0 && arr[cur] === math.max (... arr.slice(0,cur+1))){ cur-- } if(cur===0) break; Const maxInd = arr.indexof (math.max (... arr.slice(0,cur+1))); // If the maximum value is not at subscript 0, then invert it to 0. ==0){ arr = reverse(arr,0,maxInd); Res.push (maxInd+1)} // Reverse the maximum value of the current range to the target subscript arr = reverse(arr,0,cur) by reversing subscript 0 to the target subscript; res.push(cur+1); cur--; } return res; Function reverse(arr,left,right){const handleArr = arr.splice(left,right-left+1); // Reverse handlearr.reverse (); Arr. Splice (left,0,... handleArr) return arr; }};Copy the code

At this point we are done with leetcode-969- pancakes sort

If you have any questions or suggestions, please leave a comment!