heihei12305

以一道题开始吧，嘻嘻。


煎饼排序


问题描述：给定数组 A，我们可以对其进行煎饼翻转：我们选择一些正整数 k <= A.length，然后反转 A 的前 k 个元素的顺序。我们要执行零次或多次煎饼翻转（按顺序一次接一次地进行）以完成对数组 A 的排序。

返回能使 A 排序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * A.length 范围内的有效答案都将被判断为正确。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pancake-sorting

例如

输入：[3,2,4,1]
输出：[4,2,4,3]
解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 A = [3, 2, 4, 1]
第一次翻转后 (k=4): A = [1, 4, 2, 3]
第二次翻转后 (k=2): A = [4, 1, 2, 3]
第三次翻转后 (k=4): A = [3, 2, 1, 4]
第四次翻转后 (k=3): A = [1, 2, 3, 4]，此时已完成排序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pancake-sorting

题解

vector<int> pancakeSort(vector<int>& A) {
	vector<int> res;
	int n  = A.size();
	for(int i = 0;i<n-1;i++)
	{
		auto it  = max_element(A.begin(),A.end()-i);
		res.push_back(it-A.begin()+1);
		reverse(A.begin(),it+1);
		reverse(A.begin(),A.end()-i);
		res.push_back(n-i);
	}
	return res;
}

其中值得注意的就是stl中的max_element的使用，会获得最大值的迭代器，用 it-A.begin()+1 即可获得最大值的index

reverse(a,b)是将[a,b)这个范围的数调转过来，来自于 algorithm 库