{"id":2502,"date":"2018-04-15T10:51:04","date_gmt":"2018-04-15T17:51:04","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2502"},"modified":"2018-09-04T19:40:29","modified_gmt":"2018-09-05T02:40:29","slug":"leetcode-818-race-car","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-818-race-car\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 818. Race Car"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 818. Race Car (\u4e0a) - \u5237\u9898\u627e\u5de5\u4f5c EP182\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/HzlEkUt2TYs?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<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 818. Race Car (\u4e0b\uff09 - \u5237\u9898\u627e\u5de5\u4f5c EP184\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/Z39RHxb2Lew?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><strong>Problem<\/strong><\/h1>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u521d\u59cb\u4f4d\u7f6e0\u901f\u5ea6+1\uff0c\u6bcf\u6b21\u4f60\u53ef\u4ee5\u52a0\u901f\uff08\u901f\u5ea6*2\uff09\u6216\u8005\u5012\u8f66\uff08\u901f\u5ea6\u53d8\u6210-1*dir\uff09\u3002\u95ee\u6700\u5c11\u9700\u8981\u6267\u884c\u591a\u5c11\u6b65\u64cd\u4f5c\u80fd\u591f\u5230\u8fbeT\u3002<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/race-car\/description\/\">https:\/\/leetcode.com\/problems\/race-car\/description\/<\/a><\/p>\n<p>Your car starts at position 0 and speed +1 on an infinite number line.\u00a0 (Your car can go into negative positions.)<\/p>\n<p>Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).<\/p>\n<p>When you get an instruction &#8220;A&#8221;, your car does the following:\u00a0<code>position += speed, speed *= 2<\/code>.<\/p>\n<p>When you get an instruction &#8220;R&#8221;, your car does the following: if your speed is positive then\u00a0<code>speed = -1<\/code>\u00a0, otherwise\u00a0<code>speed = 1<\/code>.\u00a0 (Your position stays the same.)<\/p>\n<p>For example, after commands &#8220;AAR&#8221;, your car goes to positions 0-&gt;1-&gt;3-&gt;3, and your speed goes to 1-&gt;2-&gt;4-&gt;-1.<\/p>\n<p>Now for some target position, say the\u00a0<strong>length<\/strong>\u00a0of the shortest sequence of instructions to get there.<\/p>\n<pre class=\"crayon:false\"><strong>Example 1:<\/strong>\r\n<strong>Input:<\/strong> \r\ntarget = 3\r\n<strong>Output:<\/strong> 2\r\n<strong>Explanation:<\/strong> \r\nThe shortest instruction sequence is \"AA\".\r\nYour position goes from 0-&gt;1-&gt;3.\r\n<\/pre>\n<pre class=\"crayon:false\"><strong>Example 2:<\/strong>\r\n<strong>Input:<\/strong> \r\ntarget = 6\r\n<strong>Output:<\/strong> 5\r\n<strong>Explanation:<\/strong> \r\nThe shortest instruction sequence is \"AAARA\".\r\nYour position goes from 0-&gt;1-&gt;3-&gt;7-&gt;7-&gt;6.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>1 &lt;= target &lt;= 10000<\/code>.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h1><strong>Visualization of the Solution<\/strong><\/h1>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2517\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_norm.png\" alt=\"\" width=\"1280\" height=\"960\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_norm.png 1280w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_norm-300x225.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_norm-768x576.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_norm-1024x768.png 1024w\" sizes=\"auto, (max-width: 1280px) 100vw, 1280px\" \/> <img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2518\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_log2.png\" alt=\"\" width=\"1280\" height=\"960\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_log2.png 1280w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_log2-300x225.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_log2-768x576.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/leetcode_818_log2-1024x768.png 1024w\" sizes=\"auto, (max-width: 1280px) 100vw, 1280px\" \/><\/p>\n<h1><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2523\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/818-ep182.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/818-ep182.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/818-ep182-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/818-ep182-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/h1>\n<h1><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2749\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/818-ep184-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/818-ep184-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/818-ep184-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/818-ep184-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/h1>\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<h1><strong>Solution 1: BFS<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++\/Str<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 221 ms\r\nclass Solution {\r\npublic:\r\n  int racecar(int target) {    \r\n    queue&lt;pair&lt;int, int&gt;&gt; q;\r\n    q.push({0, 1});\r\n    unordered_set&lt;string&gt; v;\r\n    v.insert(\"0_1\");\r\n    v.insert(\"0_-1\");\r\n    int steps = 0;\r\n    while (!q.empty()) {\r\n      int size = q.size();      \r\n      while (size--) {\r\n        auto p = q.front(); q.pop();\r\n        int pos = p.first;\r\n        int speed = p.second;\r\n        {\r\n          int pos1 = pos + speed;\r\n          int speed1 = speed * 2;\r\n          pair&lt;int, int&gt; p1{pos1, speed1};\r\n          if (pos1 == target) return steps + 1;       \r\n          if (p1.first &gt; 0 &amp;&amp; p1.first &lt; 2 * target)\r\n            q.push(p1);\r\n        }\r\n        {\r\n          int speed2 = speed &gt; 0 ? -1 : 1;\r\n          pair&lt;int, int&gt; p2{pos, speed2}; \r\n          string key2 = to_string(pos) + \"_\" + to_string(speed2);\r\n          if (!v.count(key2)) {\r\n            q.push(p2);\r\n            v.insert(key2);\r\n          }\r\n        }\r\n      }\r\n      ++steps;\r\n    }\r\n    return -1;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/Int<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 16 ms\r\nclass Solution {\r\npublic:\r\n  int racecar(int target) {    \r\n    queue&lt;pair&lt;int, int&gt;&gt; q;\r\n    q.push({0, 1});\r\n    unordered_set&lt;int&gt; v;\r\n    v.insert({0, 2});\r\n    int steps = 0;\r\n    while (!q.empty()) {\r\n      int size = q.size();      \r\n      while (size--) {\r\n        auto p = q.front(); q.pop();\r\n        int pos = p.first;\r\n        int speed = p.second;                \r\n        pair&lt;int, int&gt; p1 = {pos + speed, speed * 2};\r\n        if (p1.first == target) return steps + 1;   \r\n        if (p1.first &gt; 0 &amp;&amp; p1.first + speed &lt; 2 * target)\r\n          q.push(p1);\r\n        int speed2 = speed &gt; 0 ? -1 : 1;\r\n        pair&lt;int, int&gt; p2 = {pos, speed2}; \r\n        int key = (pos &lt;&lt; 2) | (speed2 + 1);\r\n        if (!v.count(key) &amp;&amp; p2.first &gt;= target \/ 2) {\r\n          q.push(p2); \r\n          v.insert(key);\r\n        }\r\n      }\r\n      ++steps;\r\n    }\r\n    return -1;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2: DP O(TlogT)<\/strong><\/h1>\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: 4 ms\r\nclass Solution {\r\npublic:\r\n  int racecar(int target) {\r\n    m_ = vector&lt;int&gt;(target + 1, 0);\r\n    return dp(target);\r\n  }\r\nprivate:\r\n  vector&lt;int&gt; m_;\r\n  int dp(int t) {\r\n    if (m_[t] &gt; 0) return m_[t];\r\n    int n = ceil(log2(t + 1));\r\n    \/\/ AA...A (nA) best case\r\n    if (1 &lt;&lt; n == t + 1) return m_[t] = n; \r\n    \/\/ AA...AR (nA + 1R) + dp(left) \r\n    m_[t] = n + 1 + dp((1 &lt;&lt; n) - 1 - t);  \r\n    for (int m = 0; m &lt; n - 1; ++m) {\r\n      int cur = (1 &lt;&lt; (n - 1)) - (1 &lt;&lt; m);\r\n      \/\/AA...ARA...AR (n-1A + 1R + mA + 1R) + dp(left) \r\n      m_[t] = min(m_[t], n + m + 1 + dp(t - cur)); \r\n    }\r\n    return m_[t];  \r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 3: DP O(T^2)<\/strong><\/h1>\n<p>m[t][d] : min steps to reach t and facing d (0 = right, 1 = left)<\/p>\n<p>Time Complexity: O(n^2)<\/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: 469 ms\r\nconstexpr int kMaxT = 10000;\r\nint m[kMaxT + 1][2]={0};\r\n\r\nclass Solution {\r\npublic:\r\n  int racecar(int target) {\r\n    if (m[1][0] == 0) {\r\n      for (int t = 1; t &lt;= kMaxT; ++t) {\r\n        const int n = ceil(log2(t + 1));\r\n        if (1 &lt;&lt; n == t + 1) {\r\n          m[t][0] = n;\r\n          m[t][1] = n + 1;\r\n          continue;\r\n        }\r\n        const int l = (1 &lt;&lt; n) - 1 - t;\r\n        m[t][0] = n + 1 + min(m[l][1], m[l][0] + 1);\r\n        m[t][1] = n + 1 + min(m[l][0], m[l][1] + 1);\r\n        for (int i = 1; i &lt; t; ++i) { \r\n          const int mi = min(m[i][0] + 2, m[i][1] + 1);\r\n          m[t][0] = min(m[t][0], m[t - i][0] + mi);\r\n          m[t][1] = min(m[t][1], m[t - i][1] + mi);\r\n        }\r\n      }\r\n    } \r\n    return min(m[target][0], m[target][1]);\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/opt<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 361 ms\r\ntypedef unsigned char uint8;\r\nconstexpr int kMaxT = 10000;\r\nuint8 m[kMaxT + 1][2]={0};\r\n\r\ninline uint8 MIN(uint8 a, uint8 b) {\r\n  return a &lt; b ? a : b;\r\n}\r\n\r\nclass Solution {\r\npublic:\r\n  int racecar(int target) {\r\n    if (m[1][0] == 0) {\r\n      for (int t = 1; t &lt;= kMaxT; ++t) {\r\n        const int n = ceil(log2(t + 1));\r\n        if (1 &lt;&lt; n == t + 1) {\r\n          m[t][0] = n;\r\n          m[t][1] = n + 1;\r\n          continue;\r\n        }\r\n        const int l = (1 &lt;&lt; n) - 1 - t;\r\n        m[t][0] = n + 1 + MIN(m[l][1], (uint8)(m[l][0] + 1));\r\n        m[t][1] = n + 1 + MIN(m[l][0], (uint8)(m[l][1] + 1));\r\n        for (int i = 1; i &lt; t; ++i) { \r\n          const int mi = MIN(m[i][0] + 2, m[i][1] + 1);\r\n          m[t][0] = MIN(m[t][0], (uint8)(m[t - i][0] + mi));\r\n          m[t][1] = MIN(m[t][1], (uint8)(m[t - i][1] + mi));\r\n        }\r\n      }\r\n    } \r\n    return min(m[target][0], m[target][1]);\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 562 ms\r\nclass Solution {\r\n  private static int[][] m;\r\n  public int racecar(int target) {\r\n    if (m == null) {\r\n      final int kMaxT = 10000;\r\n      m = new int[kMaxT + 1][2];\r\n      for (int t = 1; t &lt;= kMaxT; ++t) {\r\n        int n = (int)Math.ceil(Math.log(t + 1) \/ Math.log(2));\r\n        if (1 &lt;&lt; n == t + 1) {\r\n          m[t][0] = n;\r\n          m[t][1] = n + 1;\r\n          continue;\r\n        }\r\n        int l = (1 &lt;&lt; n) - 1 - t;\r\n        m[t][0] = n + 1 + Math.min(m[l][1], m[l][0] + 1);\r\n        m[t][1] = n + 1 + Math.min(m[l][0], m[l][1] + 1);\r\n        for (int i = 1; i &lt; t; ++i) \r\n          for (int d = 0; d &lt;= 1; d++)\r\n            m[t][d] = Math.min(m[t][d], Math.min(\r\n                m[i][0] + 2 + m[t - i][d],\r\n                m[i][1] + 1 + m[t - i][d]));\r\n      }\r\n    } \r\n    return Math.min(m[target][0], m[target][1]);\r\n  }\r\n}<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem \u9898\u76ee\u5927\u610f\uff1a\u521d\u59cb\u4f4d\u7f6e0\u901f\u5ea6+1\uff0c\u6bcf\u6b21\u4f60\u53ef\u4ee5\u52a0\u901f\uff08\u901f\u5ea6*2\uff09\u6216\u8005\u5012\u8f66\uff08\u901f\u5ea6\u53d8\u6210-1*dir\uff09\u3002\u95ee\u6700\u5c11\u9700\u8981\u6267\u884c\u591a\u5c11\u6b65\u64cd\u4f5c\u80fd\u591f\u5230\u8fbeT\u3002 https:\/\/leetcode.com\/problems\/race-car\/description\/ Your car starts at position 0 and speed +1 on an infinite number line.\u00a0 (Your car can go into negative positions.) Your&#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,76,44],"tags":[18,77,217,42],"class_list":["post-2502","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","category-graph","category-searching","tag-dp","tag-graph","tag-hard","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2502","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=2502"}],"version-history":[{"count":26,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2502\/revisions"}],"predecessor-version":[{"id":3870,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2502\/revisions\/3870"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2502"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2502"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2502"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}