Проблема сортировки блинов
Дан массив целых чисел A
. Нам нужно отсортировать массив, выполнив серию переворотов блина.
В одном перевороте блина мы делаем следующие шаги:
- Выберите целое число
k
, где0 <= k < A.length
. - Переверните подмассив
A[0...k]
.
Например, если A = [3,2,1,4]
и мы выполнили переворот блина, выбрав k = 2
, мы инвертируем подмассив [3,2,1]
, поэтому A = [1,2,3,4]
после переворота блина в k = 2
.
Возвращает массив k-значений переворотов блинов, которые необходимо выполнить, чтобы отсортировать A
. Любой действительный ответ, который сортирует массив в пределах 10 * A.length
переворотов, будет считаться правильным.
Пример 1:
Input: A = [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. Notice that we return an array of the chosen k values of the pancake flips.
Пример 2:
Input: A = [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.
Ограничения:
1 <= A.length <= 100
1 <= A[i] <= A.length
- Все целые числа в
A
уникальны (т. е.A
— это перестановка целых чисел от1
доA.length
).
Решение
Здесь вы можете увидеть производительность моего решения (имейте в виду, что Runtime может варьироваться в зависимости от сервера):
Вы можете подписаться на меня в LinkedIn.