preface

I did not expect that one day we will spread pancake technology to the algorithm to solve the problem, of course, association, we did before the linked list flip is the reason, today we are going to achieve the array flip, a reason.

Topic describes

969. Pancake ordering

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.

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.

1 <= arr[I] <= arr. Length 1 <= arr. Length 1 <= arr. Length 1 <= arr. Length 1 <= arr.

Their thinking

  1. The summary of this problem is to flip an array of non-repeating numbers k times to get oneAn ascending array of numbersAnd we want to get the final resultA collection of the number of array elements flipped each time.
  2. So every time we flip, we need to record the number of elements that we’ve flipped and push them into an array
  3. How do I flip it?
  • Ascending array, we canFirst, scroll the largest element in the array to the frontTurn left, and then turn right,Turn to the end of the largest, which completes the ascending arrayThe flip of a number, record the number of flipped elements, since the array subscript starts at 0, the maximum value of each arrayIndex +1 is the number of records of flipped elementsAfter recording, wePop the flipped number out
  • Note: 1) There is no need to flip when the maximum subscript is last; 2) There is only need to flip when the maximum subscript is first
  • So loop through the array until you get into the arrayWe have one element left, so we don't have to flip it anymore

To the problem solving

/** * @param {number[]} arr * @return {number[]} */ var pancakeSort = function(arr) { let curArr = arr; let resArr = []; Const maxIndex = getMaxIndex(curArr); while(curarr.length >1) {const maxIndex = getMaxIndex(curArr); If (maxIndex){if(maxIndex! Push (maxIndex+1) == curarr.leng-1){// Reverse resarr.push (maxIndex+1) if the maxIndex is not the last element; reverse(curArr,maxIndex); reverse(curArr, curArr.length-1); resArr.push(curArr.length); // Reverse (curArr, curarr.leng-1); // Reverse (curarr.leng-1); resArr.push(curArr.length); } curArr.pop(); } return resArr; }; var getMaxIndex = function(arr) { let maxIndex=0; for(let i = 0; i < arr.length; i++) { if(arr[i] > arr[maxIndex]){ maxIndex = i; } } return maxIndex; } var reverse = function(arr, maxIndex) { let i = 0,j = maxIndex - i; While (I < j) {// Let temp = arr[j]; let temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; i++; j--; }}Copy the code