跳跃游戏 II

yingl · yingl · commit dc0827d9facc · 2016-08-10T17:27:59.000+08:00
diff --git a/jump_game_ii.py b/jump_game_ii.py
@@ -0,0 +1,36 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param A, a list of integers
+    # @return an integer
+    def jump(self, A):
+        # write your code here
+        '''
+        &#36825;&#39064;&#27604;&#24819;&#35937;&#30340;&#35201;&#38590;&#65292;Google&#20043;&#21518;&#25165;&#25214;&#21040;&#19968;&#20010;&#32431;&#32447;&#24615;&#30340;&#35299;&#27861;&#12290;&#20808;&#24819;&#26126;&#30333;&#19979;&#38754;2&#28857;&#65306;
+        1. &#20174;0&#20986;&#21457;&#65292;&#21482;&#38656;&#35201;1&#27493;&#23601;&#33021;&#35206;&#30422;A[1]&#21040;A[A[0]]&#65292;&#19981;&#21487;&#33021;&#26356;&#23569;
+        2. &#37027;&#20040;1 <= i <= A[0]&#33021;&#21040;&#36798;&#30340;&#26368;&#36828;&#28857;i + A[i]&#30340;&#27493;&#25968;&#19981;&#21487;&#33021;&#22810;&#20313;2&#27493;&#12290;
+        '''
+        if len(A) >= 2:
+            i, steps = 1, 1
+            curr_range = A[0] # &#24403;&#21069;&#27493;&#25968;&#35206;&#30422;&#30340;&#26368;&#36828;&#36317;&#31163;
+            next_range = A[0]  # curr_range&#20869;&#19979;&#19968;&#27493;&#33021;&#21040;&#36798;&#30340;&#26368;&#36828;&#36317;&#31163;
+            while i <= min(len(A), curr_range):
+                next_range = max(next_range, A[i] + i)
+                if i == len(A) - 1:
+                    return steps
+                if i == curr_range: # &#21040;curr_range&#21518;&#38754;&#30340;&#28857;&#24517;&#38656;&#21152;1&#27493;
+                    curr_range = next_range
+                    steps += 1
+                i += 1
+        return 0
+
+    '''
+    &#26368;&#30452;&#35266;&#30340;&#21160;&#24577;&#35268;&#21010;&#31639;&#27861;&#65292;&#22823;&#25968;&#25454;&#20250;&#36229;&#26102;&#12290;
+        ret = [2147483647] * len(A)
+        ret[0] = 0
+        for i in xrange(len(A)):
+            for j in xrange(A[i]):
+                if (i + (j + 1)) < len(A):
+                    ret[i + j + 1] = min(ret[j], ret[i] + 1)
+        return ret[-1]
+    '''
