找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1396|回复: 0
收起左侧

[刷题记录板] [leetcode] (Dec,19)每天两道题目,配 python参考解答

[复制链接]

20

主题

5

精华

586

积分

超级会员

Rank: 4

积分
586
发表于 12-19-2014 12:42 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
题目(一):Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

题目(二):Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)


图片割开参考答案:

题目(一):                                                      题目(二):







python参考解答:
题目(一):Jump Game
[code]class Solution:
    # @param A, a list of integers
    # @return a boolean
    def canJump(self, A):
        step = A[0]
        for i in range(1, len(A)):
            if step > 0:
                step -= 1
                step = max(step, A【i】)
            else:
                return False
        return True[/code]

题目(二):Jump Game II
[code]class Solution:
    # @param A, a list of integers
    # @return an integer
    # def jump(self, A):
    #     maxint = 1<<31 - 1
    #     dp = [ maxint for i in range(len(A)) ]
    #     dp[0] = 0
    #     for i in range(1, len(A)):
    #         for j in range(i):
    #             if A[j] >= (i - j):
    #                 dp【i】 = min(dp【i】, dp[j] + 1)
    #     return dp[len(A) - 1]
    # dp is time limited exceeded!
   
# We use "last" to keep track of the maximum distance that has been reached
# by using the minimum steps "ret", whereas "curr" is the maximum distance
# that can be reached by using "ret+1" steps. Thus,curr = max(i+A【i】) where 0 <= i <= last.
    def jump(self, A):   
        ret = 0
        last = 0
        curr = 0
        for i in range(len(A)):
            if i > last:
                last = curr
                ret += 1
            curr = max(curr, i+A【i】)
        return ret[/code]

本帖被以下淘专辑推荐:

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表