Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A.  We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A.  Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

Example 1:

Input: [3,2,4,1]
Output: [4,2,4,3] Explanation:  We perform 4 pancake flips, with k values 4, 2, 4, and 3. Starting state: A = [3, 2, 4, 1] After 1st flip (k=4): A = [1, 4, 2, 3] After 2nd flip (k=2): A = [4, 1, 2, 3] After 3rd flip (k=4): A = [3, 2, 1, 4] After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted.

Example 2:

Input: [1,2,3]
Output: [] Explanation: The input is already sorted, so there is no need to flip anything. Note that other answers, such as [3, 3], would also be accepted.

Note:

    1. 1 <= A.length <= 100
    2. A[i] is a permutation of [1, 2, ..., A.length]

 Idea 1. Similar to heapsort, find the maximum value, flip it first to get it to the head, then flip it to put it in the right place (the end of array), continue for the 2nd maximum value.

Time complexity: O(n^2)

Space complexity: O(1)

 1 class Solution {
 2     private void reverse(int[] A, int left, int right) {
 3         for(int i = left, j = right; i < j; ++i, --j) {
 4             int temp = A[i];
 5             A[i] = A[j];
 6             A[j] = temp;
 7         }
 8     }
 9     public List<Integer> pancakeSort(int[] A) {
10         List<Integer> result = new ArrayList<>();
11         
12         for(int max = A.length; max >= 1; --max){
13             for(int i = 0; i < max; ++i) {
14                 if(A[i] == max) {
15                     reverse(A, 0, i);
16                     reverse(A, 0, max-1);
17                     result.add(i+1);
18                     result.add(max);
19                     break;
20                 }
21             }
22         }
23         return result;
24     }
25 }

网上看到的找到max break loop 的另一种写法，简洁些，就是看着还是不习惯

 1 class Solution {
 2     private void reverse(int[] A, int left, int right) {
 3         for(int i = left, j = right; i < j; ++i, --j) {
 4             int temp = A[i];
 5             A[i] = A[j];
 6             A[j] = temp;
 7         }
 8     }
 9     public List<Integer> pancakeSort(int[] A) {
10         List<Integer> result = new ArrayList<>();
11         
12         for(int max = A.length, i; max >= 1; --max){
13             for(i = 0; A[i] != max; ++i);
14                     
15             reverse(A, 0, i);
16             reverse(A, 0, max-1);
17             result.add(i+1);
18             result.add(max);
19             
20         }
21         return result;
22     }
23 }

Idea 1.b 不需要改变数组，先sort, 记住reverse后的index, i = k - i, 官方解法

Time complexity: O(n^2)

Space complexity: O(n)

 1 class Solution {
 2     public List<Integer> pancakeSort(int[] A) {
 3         int n = A.length;
 4         List<Integer> indexA = new ArrayList<>();
 5         for(int i = 0; i < n; ++i) {
 6             indexA.add(i);
 7         }
 8         
 9         Collections.sort(indexA, (a, b) -> Integer.compare(A[b], A[a]));
10         
11         List<Integer> result = new ArrayList<>();
12         
13        
14         for(int i: indexA) {
15             for(int k: result) {
16                 if(i <= k-1) {
17                     i = k-1 - i;
18                 }
19             }
20             result.add(i+1);
21             result.add(n--);
22         }
23         return result;
24     }
25 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄