{"id":2188,"date":"2018-03-17T22:56:46","date_gmt":"2018-03-18T05:56:46","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2188"},"modified":"2018-08-30T14:22:11","modified_gmt":"2018-08-30T21:22:11","slug":"leetcode-801-minimum-swaps-to-make-sequences-increasing","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-801-minimum-swaps-to-make-sequences-increasing\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 801. Minimum Swaps To Make Sequences Increasing"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 801. Minimum Swaps To Make Sequences Increasing - \u5237\u9898\u627e\u5de5\u4f5c EP183\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/__yxFFRQAl8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1>Problem<\/h1>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e24\u4e2a\u6570\u7ec4A, B\u3002\u95ee\u6700\u5c11\u9700\u8981\u591a\u5c11\u6b21\u5bf9\u5e94\u4f4d\u7f6e\u5143\u7d20\u7684\u4ea4\u6362\u624d\u80fd\u4f7f\u5f97A\u548cB\u53d8\u6210\u5355\u8c03\u9012\u589e\u3002<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/minimum-swaps-to-make-sequences-increasing\/description\/\">https:\/\/leetcode.com\/problems\/minimum-swaps-to-make-sequences-increasing\/description\/<\/a><\/p>\n<p>We have two integer sequences\u00a0<code>A<\/code>\u00a0and\u00a0<code>B<\/code>\u00a0of the same non-zero length.<\/p>\n<p>We are allowed to swap elements\u00a0<code>A[i]<\/code>\u00a0and\u00a0<code>B[i]<\/code>.\u00a0 Note that both elements are in the same index position in their respective sequences.<\/p>\n<p>At the end of some number of swaps,\u00a0<code>A<\/code>\u00a0and\u00a0<code>B<\/code>\u00a0are both strictly increasing.\u00a0 (A sequence is\u00a0<em>strictly increasing<\/em>\u00a0if and only if\u00a0<code>A[0] &lt; A[1] &lt; A[2] &lt; ... &lt; A[A.length - 1]<\/code>.)<\/p>\n<p>Given A and B, return the minimum number of swaps to make both sequences strictly increasing.\u00a0 It is guaranteed that the given input always makes it possible.<\/p>\n<pre class=\"crayon:false \"><strong>Example:<\/strong>\r\n<strong>Input:<\/strong> A = [1,3,5,4], B = [1,2,3,7]\r\n<strong>Output:<\/strong> 1\r\n<strong>Explanation: <\/strong>\r\nSwap A[3] and B[3].  Then the sequences are:\r\nA = [1, 3, 5, 7] and B = [1, 2, 3, 4]\r\nwhich are both strictly increasing.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>A, B<\/code>\u00a0are arrays with the same length, and that length will be in the range\u00a0<code>[1, 1000]<\/code>.<\/li>\n<li><code>A[i], B[i]<\/code>\u00a0are integer values in the range\u00a0<code>[0, 2000]<\/code>.<\/li>\n<\/ul>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2539\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/801-ep183.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/801-ep183.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/801-ep183-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/03\/801-ep183-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution: Search\/DFS (TLE)<\/strong><\/h1>\n<p>Time complexity: O(2^n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: TLE 84\/102 test cases passed.\r\nclass Solution {\r\npublic:\r\n  int minSwap(vector&lt;int&gt;&amp; A, vector&lt;int&gt;&amp; B) {\r\n    int ans = INT_MAX;\r\n    dfs(A, B, 0, 0, ans);\r\n    return ans;\r\n  }\r\nprivate:\r\n  void dfs(vector&lt;int&gt;&amp; A, vector&lt;int&gt;&amp; B, int i, int c, int&amp; ans) {\r\n    if (c &gt;= ans) return;\r\n    \r\n    if (i == A.size()) {\r\n      ans = min(ans, c);\r\n      return;\r\n    }\r\n    \r\n    if (i == 0 || A[i] &gt; A[i - 1] &amp;&amp; B[i] &gt; B[i - 1])\r\n      dfs(A, B, i + 1, c, ans);\r\n    \r\n    if (i == 0 || A[i] &gt; B[i - 1] &amp;&amp; B[i] &gt; A[i - 1]) {\r\n      swap(A[i], B[i]);\r\n      dfs(A, B, i + 1, c + 1, ans);\r\n      swap(A[i], B[i]);\r\n    }\r\n  }\r\n};<\/pre>\n<p><\/div><\/div><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<p>&nbsp;<\/p>\n<h1><strong>Solution: DP<\/strong><\/h1>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 15 ms\r\nclass Solution {\r\npublic:\r\n  int minSwap(vector&lt;int&gt;&amp; A, vector&lt;int&gt;&amp; B) {\r\n    const int n = A.size();\r\n        \r\n    vector&lt;int&gt; keep(n, INT_MAX);\r\n    vector&lt;int&gt; swap(n, INT_MAX);\r\n    \r\n    keep[0] = 0;\r\n    swap[0] = 1;\r\n    \r\n    for (int i = 1; i &lt; n; ++i) {\r\n      if (A[i] &gt; A[i - 1] &amp;&amp; B[i] &gt; B[i - 1]) {\r\n        \/\/ Good case, no swapping needed.\r\n        keep[i] = keep[i - 1];\r\n    \r\n        \/\/ Swapped A[i - 1] \/ B[i - 1], swap A[i], B[i] as well\r\n        swap[i] = swap[i - 1] + 1;\r\n      }      \r\n      \r\n      if (B[i] &gt; A[i - 1] &amp;&amp; A[i] &gt; B[i - 1]) {\r\n        \/\/ A[i - 1] \/ B[i - 1] weren't swapped.\r\n        swap[i] = min(swap[i], keep[i - 1] + 1);\r\n      \r\n        \/\/ Swapped A[i - 1] \/ B[i - 1], no swap needed for A[i] \/ B[i]      \r\n        keep[i] = min(keep[i], swap[i - 1]);\r\n      }      \r\n    }\r\n      \r\n    return min(keep.back(), swap.back());\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 60 ms\r\n\"\"\"\r\nclass Solution:\r\n  def minSwap(self, A, B):\r\n    n = len(A)\r\n    dp = [[float('inf'), float('inf')] for _ in range(n)]\r\n    dp[0][0], dp[0][1] = 0, 1\r\n    for i in range(1, n):\r\n      if A[i] &gt; A[i - 1] and B[i] &gt; B[i - 1]:\r\n        dp[i][0] = dp[i - 1][0]\r\n        dp[i][1] = dp[i - 1][1] + 1\r\n      if B[i] &gt; A[i - 1] and A[i] &gt; B[i - 1]:\r\n        dp[i][0] = min(dp[i][0], dp[i - 1][1])\r\n        dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1)\r\n    return min(dp[-1])<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e24\u4e2a\u6570\u7ec4A, B\u3002\u95ee\u6700\u5c11\u9700\u8981\u591a\u5c11\u6b21\u5bf9\u5e94\u4f4d\u7f6e\u5143\u7d20\u7684\u4ea4\u6362\u624d\u80fd\u4f7f\u5f97A\u548cB\u53d8\u6210\u5355\u8c03\u9012\u589e\u3002 https:\/\/leetcode.com\/problems\/minimum-swaps-to-make-sequences-increasing\/description\/ We have two integer sequences\u00a0A\u00a0and\u00a0B\u00a0of the same non-zero length. We are allowed to swap elements\u00a0A[i]\u00a0and\u00a0B[i].\u00a0 Note that both elements are in&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,177,262],"class_list":["post-2188","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-medium","tag-multistate","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2188","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=2188"}],"version-history":[{"count":14,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2188\/revisions"}],"predecessor-version":[{"id":3785,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2188\/revisions\/3785"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2188"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2188"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2188"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}