Subject to introduce

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](Subscript starts 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[we execute4For each pancake flip, the k values are4.2.4, and3. 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], the sorting is complete.Copy the code

Example 2

Input:1.2.3[] Description: 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 to be 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)

Leetcode -969 Pancake sorting B station video

Their thinking

Think of some way to put the value of the biggest reversal at the end of the array, then they are removed from the array and continue to do this great value (why not move the minimum value to the first, because every time is first n number of reverse, the first will always be reversed, and the maximum moved to after the last one, we can not move the last one)

The problem solving steps

2. If the maximum value is the first digit, skip to step 3. If the maximum value is the last digit, skip to Step 4. Flip the entire array so that the maximum value is flipped to the last digit 4. Remove the last digit from the array 5. Repeat 1-4 until the array length is 0

The problem solving code

 var pancakeSort = function(arr) {
    const ret = []
    while (arr.length) {
        let max = getMax(arr)
        // If the maximum value is in the last digit, remove it from the array
        if(max ! == arr.length -1) {
            // If the maximum value is first, just flip the entire array
            if(max ! = =0) {
                ret.push(max + 1)
                reverse(arr, max)
            }
            ret.push(arr.length)
            reverse(arr, arr.length - 1)
        }
        arr.pop()
    }
    return ret
};

var getMax = function (arr) {
    let s = 0
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > arr[s]) s = i
    }
    return s
}

var reverse = function (arr, k) {
    let i = 0
    while (i < k) {
        [arr[i], arr[k]] = [arr[k], arr[i]]
        i++
        k--
    }
}
Copy the code

So that’s the answer to this question, Welcome to see my other article [luffy]_ ring list [Luffy]_ happy number [Luffy]_ reverse list [Luffy]_ reverse list [Luffy]_K group of flipped list [Luffy]_ rotation list [Luffy]_ pairwise swap list of nodes [Luffy]_ recent requests [Luffy]_ KTH number [Luffy]_ intimate string [Luffy]_ Lemonade change