{"id":4604,"date":"2019-01-05T20:22:41","date_gmt":"2019-01-06T04:22:41","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4604"},"modified":"2019-01-05T20:23:28","modified_gmt":"2019-01-06T04:23:28","slug":"leetcode-969-pancake-sorting","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-969-pancake-sorting\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 969. Pancake Sorting"},"content":{"rendered":"\n

Given an array A<\/code>, we can perform a pancake flip<\/em>: We choose some positive integer k<\/strong> <= A.length<\/code>, then reverse the order of the first k<\/strong> elements of A<\/code>.  We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A<\/code>.<\/p>\n\n\n\n

Return the k-values corresponding to a sequence of pancake flips that sort A<\/code>.  Any valid answer that sorts the array within 10 * A.length<\/code> flips will be judged as correct.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>[3,2,4,1]\nOutput: <\/strong>[4,2,4,3]\nExplanation: <\/strong>\nWe perform 4 pancake flips, with k values 4, 2, 4, and 3.\nStarting state: A = [3, 2, 4, 1]\nAfter 1st flip (k=4): A = [1, 4, 2, 3]\nAfter 2nd flip (k=2): A = [4, 1, 2, 3]\nAfter 3rd flip (k=4): A = [3, 2, 1, 4]\nAfter 4th flip (k=3): A = [1, 2, 3, 4], which is sorted. \n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>[1,2,3]\nOutput: <\/strong>[]\nExplanation: <\/strong>The input is already sorted, so there is no need to flip anything.\nNote that other answers, such as [3, 3], would also be accepted.\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= A.length <= 100<\/code><\/li>
  2. A[i]<\/code> is a permutation of [1, 2, ..., A.length]<\/code><\/li><\/ol>\n\n\n\n
    Solution: Simulation<\/strong><\/h2>\n\n\n\n
    Put the largest element to its position. Each element requires two flips
    e.g. [3, 2, 4, 1]
    largest element: 4, index: 2
    flip1: [4, 2, 3, 1]
    flip2: [1, 3, 2, 4]
    Repeat for [1, 3, 2]…<\/p>\n\n\n\n
    Time complexity: O(n^2)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 8 ms\nclass Solution {\npublic:\n  vector pancakeSort(vector& A) {\n    const int n = A.size();\n    vector ans;\n    for (int i = 0; i < n - 1; ++i) {\n      int p = max_element(begin(A), end(A) - i) - begin(A);\n      ans.push_back(p + 1);\n      std::reverse(begin(A), begin(A) + p + 1);\n      ans.push_back(n - i);\n      std::reverse(begin(A), begin(A) + n - i);\n    }    \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A.  We want to perform…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[177,23],"class_list":["post-4604","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-medium","tag-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4604","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4604"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4604\/revisions"}],"predecessor-version":[{"id":4606,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4604\/revisions\/4606"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4604"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4604"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4604"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}