This is my 32nd day of participating in the First Challenge 2022

preface

  • Some love each other, some drive at night to watch the sea, someleetcodeYou can’t do the first one, so you can see,leetcodeThe problem has weight. Today we’re going to meet them

Title address

Pancakes sorting

Subject to introduce

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.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 All integers in arr are different (i.e., arr is a permutation of integers from 1 to arr.Copy the code

Class selection sort

Train of thought

Given an element with an index of nindex, we can put it at the end of the element by doing two pancake sorts:

The first step is to select k=index+1, and then invert the rotor array arr[0…k−1], at which point the element is placed at the head.

The second step is to select k=n, where n is the length of the array arr, and then reverse the entire array so that the element has been placed at the end.

In the above two steps, we can put the maximum value of the current array to the end, and then use the array with the tail element removed as the new processing object. Repeat the above operation until the length of the processing object is equal to one. At this point, the original array has been sorted, and the total operands required are 2×(n−1), which meets the requirements of the problem. If the maximum value is already at the tail, we can omit the corresponding operation.

solution

var pancakeSort = function(arr) { const ret = []; for (let n = arr.length; n > 1; n--) { let index = 0; for (let i = 1; i < n; i++) { if (arr[i] >= arr[index]) { index = i; } } if (index === n - 1) { continue; } reverse(arr, index); reverse(arr, n - 1); ret.push(index + 1); ret.push(n); } return ret; } const reverse = (arr, end) => { for (let i = 0, j = end; i < j; i++, j--) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }};Copy the code

Write in the last

  • I hope you find it rewarding