Look a hundred times beauty, beauty is not necessarily yours. But if you run the algorithm a hundred times, the knowledge is yours

Who can have nine floors? No need to get up!

Title address

The title

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 from0Start)

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)

Their thinking

  • Find the index of the largest number firsti, and place the largest number at the head of the array and write down the first flipk = i + 1
  • Flip the entire array, placing the largest number at the end of the array and writing down the valuekEquals the length of the arraylen
  • Because the largest number has already been flipped, we don’t have to worry about tails the next time we flip
  • Repeat the above operation for the excluded part to complete the problem solving

The problem solving code

var pancakeSort = function(arr) {
    let len = arr.length
    if(! len||len ==1) return arr
    let list = []
    let max = findMaxIndex(arr,len)
    
    while(len){
            if(max<len){
                list.push(max+1)
                for(let i=0,j=max; i<=max; i++){if(i<j){
                    [ arr[i],arr[j]] =[arr[j],arr[i]]
                    }
                    j--
                }
                for(let i=0,j=len-1; i<len; i++){if(i<j){
                    [ arr[i],arr[j]] =[arr[j],arr[i]]
                    }
                    j--
                }
                list.push(len)
            }
            len--
            max = findMaxIndex(arr,len)
    }
    return list
};

var findMaxIndex = function(arr,len){
    let max = 0
    for(let i=0; i<len; i++){if(arr[i]>arr[max]){
            max = i
        }
    }
    return max
}
Copy the code

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