LeetCode 969. Pancake Sorting

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

题目描述： [https://leetcode.com/problems/pancake-sorting/][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 };

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

[https_leetcode.com_problems_pancake-sorting]: https://leetcode.com/problems/pancake-sorting/

发表评论取消回复

表情：

评论列表（有 0 条评论，195人围观）

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

相关阅读

相关 LeetCode（Sorting)1859. Sorting the Sentence

1.问题 A sentence is a list of words that are separated by a single space with no leadi

女爷i/ 2023年09月23日 23:52/ 0 赞/ 121 阅读

相关 LeetCode（Sorting)2418. Sort the People

1.问题 You are given an array of strings names, and an array heights that consists of d

旧城等待，/ 2023年09月23日 23:23/ 0 赞/ 81 阅读

相关 leetcode 专题—sort

此将主要将leetcode中sort专题的解答都放在这里，后续会慢慢加入一：leetcode179 [Largest Number][] 题目： Given a lis

朱雀/ 2022年08月08日 05:30/ 0 赞/ 177 阅读

相关 Leetcode: Sort Colors

题目： Given an array with n objects colored red, white or blue, sort them so that object

红太狼/ 2022年08月07日 12:47/ 0 赞/ 131 阅读

相关 Sort Colors--LeetCode

题目： Given an array with n objects colored red, white or blue, sort them so that objec

向右看齐/ 2022年08月07日 11:44/ 0 赞/ 86 阅读

相关 LeetCode148—Sort List

原题 [原题链接][Link 1] > Sort a linked list in O(n log n) time using constant space compl

素颜马尾好姑娘i/ 2022年07月15日 03:16/ 0 赞/ 224 阅读

相关 golang 算法之 pancake

// Pancake Sort in Golang package main import "fmt" func main(

拼搏现实的明天。/ 2022年06月08日 12:25/ 0 赞/ 165 阅读

相关 LeetCode刷题---969. 煎饼排序

题目要求给定数组 `A`，我们可以对其进行煎饼翻转：我们选择一些正整数 `k <= A.length`，然后反转 `A` 的前 `k` 个元素的顺序。我们要执行零次或多

心已赠人/ 2022年03月29日 11:00/ 0 赞/ 186 阅读

相关 leetcode [148]Sort List

Sort a linked list in O(n log n) time using constant space complexity. Example 1:

你的名字/ 2021年12月07日 14:21/ 0 赞/ 237 阅读

相关 LeetCode 969. Pancake Sorting

题目描述： [https://leetcode.com/problems/pancake-sorting/][https_leetcode.com_problems_panca

我会带着你远行/ 2021年11月29日 05:50/ 0 赞/ 196 阅读