Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/969.html
969. Pancake Sorting (Medium)
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.
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 <= A.length <= 100
A[i]
is a permutation of[1, 2, ..., A.length]
Companies:
Square
Solution 1.
-
class Solution { public List<Integer> pancakeSort(int[] A) { List<Integer> list = new ArrayList<Integer>(); int length = A.length; for (int i = length; i >= 1; i--) { if (A[i - 1] != i) { int flipIndex = 0; for (int j = length - 1; j >= 0; j--) { if (A[j] == i) { flipIndex = j; break; } } if (flipIndex > 0) { pancakeFlip(A, flipIndex); list.add(flipIndex + 1); } pancakeFlip(A, i - 1); list.add(i); } } return list; } public void pancakeFlip(int[] array, int index) { int left = 0, right = index; while (left < right) { int temp = array[left]; array[left] = array[right]; array[right] = temp; left++; right--; } } } ############ class Solution { public List<Integer> pancakeSort(int[] arr) { int n = arr.length; List<Integer> ans = new ArrayList<>(); for (int i = n - 1; i > 0; --i) { int j = i; for (; j > 0 && arr[j] != i + 1; --j) ; if (j < i) { if (j > 0) { ans.add(j + 1); reverse(arr, j); } ans.add(i + 1); reverse(arr, i); } } return ans; } private void reverse(int[] arr, int j) { for (int i = 0; i < j; ++i, --j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } }
-
// OJ: https://leetcode.com/problems/pancake-sorting // Time: O(N^2) // Space: O(1) class Solution { public: vector<int> pancakeSort(vector<int>& A) { vector<int> ans; for (int i = A.size(); i > 0; --i) { int j = i - 1; for (; j >= 0 && A[j] != i; --j); reverse(A.begin(), A.begin() + j + 1); ans.push_back(j + 1); reverse(A.begin(), A.begin() + i); ans.push_back(i); } return ans; } };
-
class Solution: def pancakeSort(self, arr: List[int]) -> List[int]: def reverse(arr, j): i = 0 while i < j: arr[i], arr[j] = arr[j], arr[i] i, j = i + 1, j - 1 n = len(arr) ans = [] for i in range(n - 1, 0, -1): j = i while j > 0 and arr[j] != i + 1: j -= 1 if j < i: if j > 0: ans.append(j + 1) reverse(arr, j) ans.append(i + 1) reverse(arr, i) return ans ############ class Solution(object): def pancakeSort(self, A): """ :type A: List[int] :rtype: List[int] """ N = len(A) res = [] for x in range(N, 0, -1): i = A.index(x) res.extend([i + 1, x]) A = A[:i:-1] + A[:i] return res
-
func pancakeSort(arr []int) []int { var ans []int n := len(arr) reverse := func(j int) { for i := 0; i < j; i, j = i+1, j-1 { arr[i], arr[j] = arr[j], arr[i] } } for i := n - 1; i > 0; i-- { j := i for ; j > 0 && arr[j] != i+1; j-- { } if j < i { if j > 0 { ans = append(ans, j+1) reverse(j) } ans = append(ans, i+1) reverse(i) } } return ans }
-
function pancakeSort(arr: number[]): number[] { let ans = []; for (let n = arr.length; n > 1; n--) { let index = 0; for (let i = 1; i < n; i++) { if (arr[i] >= arr[index]) { index = i; } } if (index == n - 1) continue; reverse(arr, index); reverse(arr, n - 1); ans.push(index + 1); ans.push(n); } return ans; } function reverse(nums: Array<number>, end: number): void { for (let i = 0, j = end; i < j; i++, j--) { [nums[i], nums[j]] = [nums[j], nums[i]]; } }
-
impl Solution { pub fn pancake_sort(mut arr: Vec<i32>) -> Vec<i32> { let mut res = vec![]; for n in (1..arr.len()).rev() { let mut max_idx = 0; for idx in 0..=n { if arr[max_idx] < arr[idx] { max_idx = idx; } } if max_idx != n { if max_idx != 0 { arr[..=max_idx].reverse(); res.push(max_idx as i32 + 1); } arr[..=n].reverse(); res.push(n as i32 + 1); } } res } }