Сложность: medium
Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов.
При одном перевороте блина мы выполняем следующие шаги:
Выбираем целое число k, где 1 <= k <= arr.length.
Переворачиваем подмассив arr[0...k-1] (индексация с 0).
Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3.
Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным.
Пример:
Input: arr = [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: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.
👨💻 Алгоритм:
1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0
] (в Python).
2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего.
3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте.
😎 Решение:
class Solution {
func pancakeSort(_ A: [Int]) -> [Int] {
var A = A
var ans = [Int]()
for valueToSort in stride(from: A.count, to: 0, by: -1) {
let index = find(A, valueToSort)
if index == valueToSort - 1 { continue }
if index != 0 {
ans.append(index + 1)
flip(&A, index + 1)
}
ans.append(valueToSort)
flip(&A, valueToSort)
}
return ans
}
private func flip(_ sublist: inout [Int], _ k: Int) {
var i = 0
while i < k / 2 {
let temp = sublist[i]
sublist[i] = sublist[k - i - 1]
sublist[k - i - 1] = temp
i += 1
}
}
private func find(_ a: [Int], _ target: Int) -> Int {
for i in 0..<a.count {
if a[i] == target {
return i
}
}
return -1
}
}Ставь 👍 и забирай 📚 Базу знаний