烧饼排序算法
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准,解决了之前 chatGPT 翻译可能出错的问题~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
969. Pancake Sorting | 969. 煎饼排序 | 🟠 |
力扣第 969 题「煎饼排序」是个很有意思的实际问题:假设盘子上有 n
块面积大小不一的烧饼,你如何用一把锅铲进行若干次翻转,让这些烧饼的大小有序(小的在上,大的在下)?
![](/algo/images/pancakeSort/1.jpg)
设想一下用锅铲翻转一堆烧饼的情景,其实是有一点限制的,我们每次只能将最上面的若干块饼子翻转:
![](/algo/images/pancakeSort/2.png)
我们的问题是,如何使用算法得到一个翻转序列,使得烧饼堆变得有序?
首先,需要把这个问题抽象,用数组来表示烧饼堆:
969. 煎饼排序 | 力扣 | LeetCode |
给你一个整数数组 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]
。
以数组形式返回能使 arr
有序的煎饼翻转操作所对应的 k
值序列。任何将数组排序且翻转次数在 10 * arr.length
范围内的有效答案都将被判断为正确。
示例 1:
输入:[3,2,4,1] 输出:[4,2,4,3] 解释: 我们执行 4 次煎饼翻转,k 值分别为 4,2,4,和 3。 初始状态 arr = [3, 2, 4, 1] 第一次翻转后(k = 4):arr = [1, 4, 2, 3] 第二次翻转后(k = 2):arr = [4, 1, 2, 3] 第三次翻转后(k = 4):arr = [3, 2, 1, 4] 第四次翻转后(k = 3):arr = [1, 2, 3, 4],此时已完成排序。
示例 2:
输入:[1,2,3] 输出:[] 解释: 输入已经排序,因此不需要翻转任何内容。 请注意,其他可能的答案,如 [3,3] ,也将被判断为正确。
提示:
1 <= arr.length <= 100
1 <= arr[i] <= arr.length
arr
中的所有整数互不相同(即,arr
是从1
到arr.length
整数的一个排列)
如何解决这个问题呢?其实类似上篇文章 递归反转链表的一部分,这也是需要递归思想的。
一、思路分析
为什么说这个问题有递归性质呢?比如说我们需要实现这样一个函数:
// cakes 是一堆烧饼,函数会将前 n 个烧饼排序
void sort(int[] cakes, int n);
// cakes 是一堆烧饼,函数会将前 n 个烧饼排序
void sort(int cakes[], int n);
# cakes 是一堆烧饼,函数会将前 n 个烧饼排序
def sort(cakes: List[int], n: int):
// cakes 是一堆烧饼,函数会将前 n 个烧饼排序
func sort(cakes []int, n int) {}
// cakes 是一堆烧饼,函数会将前 n 个烧饼排序
var sort = function(cakes, n) {
};
如果我们找到了前 n
个烧饼中最大的那个,然后设法将这个饼子翻转到最底下:
![](/algo/images/pancakeSort/3.jpg)
那么,原问题的规模就可以减小,递归调用 pancakeSort(A, n-1)
即可:
![](/algo/images/pancakeSort/4.jpg)
接下来,对于上面的这 n - 1
块饼,如何排序呢?还是先从中找到最大的一块饼,然后把这块饼放到底下,再递归调用 pancakeSort(A, n-1-1)
……
你看,这就是递归性质,总结一下思路就是:
1、找到 n
个饼中最大的那个。
2、把这个最大的饼移到最底下。
3、递归调用 pancakeSort(A, n - 1)
。
base case:n == 1
时,排序 1 个饼时不需要翻转。
那么,最后剩下个问题,如何设法将某块烧饼翻到最后呢?
其实很简单,比如第 3 块饼是最大的,我们想把它换到最后,也就是换到第 n
块。可以这样操作:
1、用锅铲将前 3 块饼翻转一下,这样最大的饼就翻到了最上面。
2、用锅铲将前 n
块饼全部翻转,这样最大的饼就翻到了第 n
块,也就是最后一块。
以上两个流程理解之后,基本就可以写出解法了,不过题目要求我们写出具体的反转操作序列,这也很简单,只要在每次翻转烧饼时记录下来就行了。
二、代码实现
只要把上述的思路用代码实现即可,唯一需要注意的是,数组索引从 0 开始,而我们要返回的结果是从 1 开始算的。
class Solution {
// 记录反转操作序列
LinkedList<Integer> res = new LinkedList<>();
public List<Integer> pancakeSort(int[] cakes) {
sort(cakes, cakes.length);
return res;
}
void sort(int[] cakes, int n) {
// base case
if (n == 1) return;
// 寻找最大饼的索引
int maxCake = 0;
int maxCakeIndex = 0;
for (int i = 0; i < n; i++)
if (cakes[i] > maxCake) {
maxCakeIndex = i;
maxCake = cakes[i];
}
// 第一次翻转,将最大饼翻到最上面
reverse(cakes, 0, maxCakeIndex);
res.add(maxCakeIndex + 1);
// 第二次翻转,将最大饼翻到最下面
reverse(cakes, 0, n - 1);
res.add(n);
// 递归调用
sort(cakes, n - 1);
}
void reverse(int[] arr, int i, int j) {
while (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
}
}
class Solution {
public:
// 记录反转操作序列
vector<int> res;
vector<int> pancakeSort(vector<int>& cakes) {
sort(cakes, cakes.size());
return res;
}
void sort(vector<int>& cakes, int n) {
// base case
if (n == 1) return;
// 寻找最大饼的索引
int maxCake = 0;
int maxCakeIndex = 0;
for (int i = 0; i < n; i++)
if (cakes[i] > maxCake) {
maxCakeIndex = i;
maxCake = cakes[i];
}
// 第一次翻转,将最大饼翻到最上面
reverse(cakes, 0, maxCakeIndex);
res.push_back(maxCakeIndex + 1);
// 第二次翻转,将最大饼翻到最下面
reverse(cakes, 0, n - 1);
res.push_back(n);
// 递归调用
sort(cakes, n - 1);
}
void reverse(vector<int>& arr, int i, int j) {
while (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
}
};
from typing import List
class Solution:
def pancakeSort(self, cakes: List[int]) -> List[int]:
# 记录反转操作序列
self.res = []
self.sort(cakes, len(cakes))
return self.res
def sort(self, cakes: List[int], n: int) -> None:
# base case
if n == 1:
return
# 寻找最大饼的索引
max_cake = 0
max_cake_index = 0
for i in range(n):
if cakes[i] > max_cake:
max_cake_index = i
max_cake = cakes[i]
# 第一次翻转,将最大饼翻到最上面
self.reverse(cakes, 0, max_cake_index)
self.res.append(max_cake_index + 1)
# 第二次翻转,将最大饼翻到最下面
self.reverse(cakes, 0, n - 1)
self.res.append(n)
# 递归调用
self.sort(cakes, n - 1)
def reverse(self, arr: List[int], i: int, j: int) -> None:
while i < j:
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
func pancakeSort(cakes []int) []int {
res := []int{}
sort(cakes, len(cakes), &res)
return res
}
func sort(cakes []int, n int, res *[]int) {
// base case
if n == 1 {
return
}
// 寻找最大饼的索引
maxCake := 0
maxCakeIndex := 0
for i := 0; i < n; i++ {
if cakes[i] > maxCake {
maxCakeIndex = i
maxCake = cakes[i]
}
}
// 第一次翻转,将最大饼翻到最上面
reverse(cakes, 0, maxCakeIndex)
*res = append(*res, maxCakeIndex+1)
// 第二次翻转,将最大饼翻到最下面
reverse(cakes, 0, n-1)
*res = append(*res, n)
// 递归调用
sort(cakes, n-1, res)
}
func reverse(arr []int, i int, j int) {
for i < j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
var pancakeSort = function(cakes) {
// 记录反转操作序列
const res = [];
const sort = function(cakes, n) {
// base case
if (n == 1) return;
// 寻找最大饼的索引
let maxCake = 0;
let maxCakeIndex = 0;
for (let i = 0; i < n; i++)
if (cakes[i] > maxCake) {
maxCakeIndex = i;
maxCake = cakes[i];
}
// 第一次翻转,将最大饼翻到最上面
reverse(cakes, 0, maxCakeIndex);
res.push(maxCakeIndex + 1);
// 第二次翻转,将最大饼翻到最下面
reverse(cakes, 0, n - 1);
res.push(n);
// 递归调用
sort(cakes, n - 1);
};
const reverse = function(arr, i, j) {
while (i < j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
};
sort(cakes, cakes.length);
return res;
};
通过刚才的详细解释,这段代码应该是很清晰了。
算法的时间复杂度很容易计算,因为递归调用的次数是 n
,每次递归调用都需要一次 for 循环,时间复杂度是 O(n),所以总的复杂度是 O(n^2)。
最后,我们可以思考一个问题:按照我们这个思路,得出的操作序列长度应该为 2(n - 1)
,因为每次递归都要进行 2 次翻转并记录操作,总共有 n
层递归,但由于 base case 直接返回结果,不进行翻转,所以最终的操作序列长度应该是固定的 2(n - 1)
。
显然,这个结果不是最优的(最短的),比如说一堆煎饼 [3,2,4,1]
,我们的算法得到的翻转序列是 [3,4,2,3,1,2]
,但是最快捷的翻转方法应该是 [2,3,4]
:
初始状态 :[3,2,4,1]
翻前 2 个:[2,3,4,1]
翻前 3 个:[4,3,2,1]
翻前 4 个:[1,2,3,4]
如果要求你的算法计算排序烧饼的最短操作序列,你该如何计算呢?或者说,解决这种求最优解法的问题,核心思路什么,一定需要使用什么算法技巧呢?
不妨分享一下你的思考。
《labuladong 的算法笔记》已经出版,关注公众号查看详情;后台回复「全家桶」可下载配套 PDF 和刷题全家桶:
![](/algo/images/souyisou2.png)