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

969. Pancake ordering

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.

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

Example 3

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

prompt

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= arr.length
  • All integers in arr are different (that is, arr is a permutation of integers from 1 to arr.length

Answer key

Analog + pointer

Pancake flipping sort, algorithm can calculate the pancake, ha ha. fun

Look at the example, a little confused. First analysis of the example given data arr =,2,4,1 [3] arr =,2,4,1 [3] arr =,2,4,1 [3], eventually sort arr = [1, 2, 3, 4] arr = [1, 2, 3, 4] arr = [1, 2, 3, 4]

The pancake sort can be understood as:

  • Arr =[3,2,4,1] arr=[3,2,4,1] arr=[3,2,4,1] idxidxidx; Reverse array [0, IDx][0, IDx][0, IDx][0, IDx], get: ,2,3,1 arr = [4] arr =,2,3,1 [4] arr =,2,3,1 [4], the entire array inversion, namely interval [0, arr. Length – 1] [0, arr. Length – 1] [0, arr. Length – 1), are: ,3,2,4 arr = [1] arr =,3,2,4 [1] arr =,3,2,4 [1]
  • Arr =[1,3,2,4] arr=[1,3,2,4] arr=[1,3,2,4] subscript idxidxidx; Reverse array [0, IDx][0, IDx][0, IDx][0, IDx], get: ,1,2,4 arr = [3] arr =,1,2,4 [3] arr =,1,2,4 [3], the entire array – 1 turn, namely interval [0, arr. Length – 2] [0, arr. Length – 2] [0, arr. Length – 2], are: Arr =,1,3,4 [2] arr =,1,3,4 [2] arr =,1,3,4 [2]

It’s a bit like bubble sorting, using two pancake flips at a time to put the last one in place; O(n2)O(n^2)O(n2)

Edit the code as follows

var pancakeSort = function (arr) {
  const len = arr.length
  let result = []
  for (let i = len - 1; i >= 0; i--) {
    let idx = 0
    let max = arr[0]
    for (let j = 0; j <= i; j++) {
      if (arr[j] > max) {
        max = arr[j]
        idx = j
      }
    }

    reverse(0, idx)
    reverse(0, i)
    result.push(idx+1, i+1)}return result

  function reverse(left, right) {
    while (left < right) {
      const t = arr[left]
      arr[left] = arr[right]
      arr[right] = t
      left++
      right--
    }
  }
}
Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section