969. Pancake Sorting

• 969. Pancake Sorting
  • Description
  • Intuition
    • Four Step Flip Solution
  • Pitfall
  • Solution

Description

Here

Intuition

Four Step Flip Solution

假设我们有如下的partial solution

nums = [6, 7, 3, 1, 2, 4, 5]
              ^  ^
              |  |
        leftSort

满足条件

1. [leftSort + 1, nums.length - 1] 是sorted
2. 现在我们考虑leftSort

Step 1. 找到k，最后一个nums[k] < target Step 2. flip(k + 1) -> [2, 1, 3, 7, 6, 4, 5] Step 3. flip(k - leftSort) -> [1, 2, 3, 7, 6, 4, 5] Step 4. flip(k - leftSort + 1) -> [3, 2, 1, 7, 6, 4, 5] Step 5. flip(k + 1) -> [6, 7, 1, 2, 3, 4, 5]

Pitfall

Solution

Solution