{"id":2602,"date":"2018-08-19T21:26:15","date_gmt":"2018-08-19T13:26:15","guid":{"rendered":"https:\/\/nodelay.xyz\/?p=2602"},"modified":"2018-08-19T21:26:15","modified_gmt":"2018-08-19T13:26:15","slug":"leetcode-403-frog-jump","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2602","title":{"rendered":"LeetCode 403. Frog Jump"},"content":{"rendered":"<p>A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.<br \/>\nGiven a list of stones&#8217; positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.<br \/>\nIf the frog&#8217;s last jump was\u00a0<i>k<\/i>\u00a0units, then its next jump must be either\u00a0<i>k<\/i>\u00a0&#8211; 1,\u00a0<i>k<\/i>, or\u00a0<i>k<\/i>\u00a0+ 1 units. Note that the frog can only jump in the forward direction.<br \/>\n\u601d\u8def\uff1a\u8fd9\u4e2a\u9898\u76ee\u53ef\u4ee5\u770b\u4f5c\u662f\u52a8\u6001\u89c4\u5212\u3002\u9752\u86d9\u7684\u4e00\u4e2a\u72b6\u6001\u53ef\u4ee5\u8868\u793a\u4e3a{\u5f53\u524d\u7684k\uff0c\u5f53\u524d\u7684\u4f4d\u7f6e(\u53ef\u4ee5\u7528stone\u7684\u7d22\u5f15\u8868\u793a)}\uff0c\u6700\u521d\u7684\u65f6\u5019\u72b6\u6001\u5c31\u662f{ 1, 0 }\u3002\u5728\u67d0\u4e00\u4e2a\u72b6\u6001\u4e0b\uff0c\u9752\u86d9\u53ef\u4ee5\u5c1d\u8bd5\u5411\u524d\u79fb\u52a8{k-1, k, k+1}\u6b65\uff0c\u5982\u679c\u80fd\u6210\u529f\u8df3\u5230\u90a3\u5c31\u8fdb\u5165\u4e86\u4e0b\u4e00\u4e2a\u72b6\u6001\u3002\u8981\u6ce8\u610f\u7684\u662f\u8fd9\u79cd\u72b6\u6001\u7684\u904d\u5386\u662f\u6709\u91cd\u590d\u7684\uff0c\u6240\u4ee5\u9700\u8981\u4e00\u4e2a\u4e1c\u897f\u8bb0\u5f55\u5df2\u7ecf\u5c1d\u8bd5\u8fc7\uff08\u5f53\u7136\u662f\u5c1d\u8bd5\u5931\u8d25\u7684\uff0c\u4e0d\u7136\u76f4\u63a5return true)\u7684\u72b6\u6001\u4eec\uff0c\u4e0d\u7136\u5f88\u5bb9\u6613\u8d85\u65f6\u3002<br \/>\n\u4e3a\u4e86\u907f\u514d\u6808\u6ea2\u51fa\uff0c\u4e0b\u6587\u7684\u89e3\u6cd5\u76f4\u63a5\u7528stack\u6a21\u62df\u51fd\u6570\u7684\u6808\u8c03\u7528\u3002<\/p>\n<pre class=\"lang:default decode:true  \">class Solution {\npublic:\n    bool canCross(vector&lt;int&gt;&amp; stones) {\n        if (stones.empty())\n            return false;\n        else if (stones.size() == 1)\n            return true;\n        \/\/ state { k, index, has_traversed }\n        stack&lt;tuple&lt;int, int, bool&gt;&gt; states;\n        unordered_map&lt;int, set&lt;int&gt;&gt; visited;\n        states.push({ 1, 0, false });\n        while (!states.empty())\n        {\n            if (std::get&lt;2&gt;(states.top()) == true)\n            {\n                \/\/ pop state (like recursive function returning)\n                states.pop();\n                continue;\n            }\n            int last_k = std::get&lt;0&gt;(states.top());\n            int last_pos_idx = std::get&lt;1&gt;(states.top());\n            if (visited[last_k].count(last_pos_idx) &gt; 0)\n            {\n                \/\/ avoid duplicated state entry\n                states.pop();\n                continue;\n            }\n            std::get&lt;2&gt;(states.top()) = true;\n            visited[last_k].insert(last_pos_idx);\n            if (last_pos_idx == stones.size() - 1)\n                return true;\n            for (int step = last_k - 1; step &lt;= last_k + 1; ++step)\n            {\n                if (step == 0) continue;\n                if (last_pos_idx == 0 &amp;&amp; step != 1) continue; \/\/ can only move 1 step at the beginning\n                int next_stone = stones[last_pos_idx] + step;\n                for (int j = last_pos_idx + 1; j &lt; stones.size(); ++j)\n                {\n                    if (stones[j] &gt; next_stone) break;\n                    if (stones[j] == next_stone)\n                    {\n                        states.push({ step, j , false}); \/\/Push state of the next stone\n                    }\n                }\n            }\n        }\n        return false;\n    }\n};\n<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a list of stones&#8217; positions (in units) in sorted ascending order, determine if the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[65,141],"class_list":["post-2602","post","type-post","status-publish","format-standard","hentry","category-technical","tag-leetcode","tag-141"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2602","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2602"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2602\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2602"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2602"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2602"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}