LeetCode - Algorithms - 969. Pancake Sorting

Just mark it. I can’t understand the solution of leetcode.
It is NP-hard problem. Bill Gates had a paper on this topic.

Problem

煎饼排序

969. Pancake Sorting

Java

LeetCode Solution

Approach 1: Sort Largest to Smallest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> pancakeSort(int[] A) {
        List<Integer> ans = new ArrayList<Integer>();
        int N = A.length;

        Integer[] B = new Integer[N];
        for (int i = 0; i < N; ++i)
            B[i] = i+1;
        Arrays.sort(B, (i, j) -> A[j-1] - A[i-1]);

        for (int i: B) {
            for (int f: ans)
                if (i <= f)
                    i = f+1 - i;
            ans.add(i);
            ans.add(N--);
        }

        return ans;
    }   
}

Submission Detail

  • 215 / 215 test cases passed.
  • Runtime: 6 ms, faster than 6.90% of Java online submissions for Pancake Sorting.
  • Memory Usage: 42.8 MB, less than 5.26% of Java online submissions for Pancake Sorting.

Rosetta Code

To my surprise, the solution of Rosetta Code Sorting algorithms/Pancake sort can’t pass on leetcode.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * Sorting algorithms/Pancake sort
 * https://rosettacode.org/wiki/Sorting_algorithms/Pancake_sort
 */
public class PancakeSortRosetta {
	int[] heap;

	public String toString() {
		String info = "";
		for (int x : heap)
			info += x + " ";
		return info;
	}

	public void flip(int n, List<Integer> list) {
		for (int i = 0; i < (n + 1) / 2; ++i) {
			int tmp = heap[i];
			heap[i] = heap[n - i];
			heap[n - i] = tmp;
		}
		list.add(n);
		System.out.println("flip(0.." + n + "): " + toString());
	}

	public int[] minmax(int n) {
		int xm, xM;
		xm = xM = heap[0];
		int posm = 0, posM = 0;

		for (int i = 1; i < n; ++i) {
			if (heap[i] < xm) {
				xm = heap[i];
				posm = i;
			} else if (heap[i] > xM) {
				xM = heap[i];
				posM = i;
			}
		}
		return new int[] { posm, posM };
	}

	public void sort(int n, int dir, List<Integer> list) {
		if (n == 0)
			return;

		int[] mM = minmax(n);
		int bestXPos = mM[dir];
		int altXPos = mM[1 - dir];
		boolean flipped = false;

		if (bestXPos == n - 1) {
			--n;
		} else if (bestXPos == 0) {
			flip(n - 1, list);
			--n;
		} else if (altXPos == n - 1) {
			dir = 1 - dir;
			--n;
			flipped = true;
		} else {
			flip(bestXPos, list);
		}
		sort(n, dir, list);

		if (flipped) {
			flip(n, list);
		}
	}

	public List<Integer> pancakeSort(int[] A) {
		List<Integer> list = new ArrayList<Integer>();
		heap = A;
		sort(A.length, 1, list);
		return list;
	}

	public static void main(String[] args) {
		int[] arr = {3, 2, 4, 1};
		PancakeSortRosetta pancakesort = new PancakeSortRosetta();
		List<Integer> list = pancakesort.pancakeSort(arr);
		System.out.println("["+list.stream().map(Object::toString).collect(Collectors.joining(","))+"]");
		Stream.of(pancakesort.heap).map(Arrays::toString).forEach(System.out::println);
	}
}

ref