题目描述: https://leetcode.com/problems/pancake-sorting/
1 class Solution { 2 public: 3 vector<int> pancakeSort(vector<int>& A) { 4 // 思路:A中的元素为[1,2,3...,n]的置换,我们知道排序后的最大数为n。从最大数开始, 5 // 找到他的正确位置: 先找到他的当前位置k,逆转数组的前k个数,n此时位于数组头部, 6 // 然后逆转数组的前n个数,使得n到无序区的尾部。n-1同理。最多需要逆转2*n-3次。 7 vector<int> ans; 8 int n=A.size(); 9 for(int i=n-1; i>0; --i){ 10 // A中的元素为[1,2,3...,n]的置换,所以排序后A[i]上的数应为i+1 11 if(A[i] != i+1){ 12 int k; 13 for(k=0; k<i; ++k) 14 if(A[k] == i+1) 15 break; 16 // 不在头部,逆转到头部 17 if(k > 0) { 18 reverse(A.begin(), A.begin()+k+1); 19 ans.push_back(k+1); 20 } 21 // 将位于头部的数 i+1 逆转到位置 i 22 reverse(A.begin(), A.begin()+i+1); 23 ans.push_back(i+1); 24 } 25 } 26 return ans; 27 } 28 };