LeetCode 969. Pancake Sorting

我会带着你远行 2021-11-29 05:50 241阅读 0赞

题目描述: https://leetcode.com/problems/pancake-sorting/

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

转载于:https://www.cnblogs.com/sclczk/p/11161993.html

发表评论

表情:
评论列表 (有 0 条评论,241人围观)

还没有评论,来说两句吧...

相关阅读