频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
45. Jump Game II Leetcode Python
2019-11-13 09:25:10         来源:hyperbolechi的专栏  
收藏   我要投稿

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.)



This is also a greedy problem the difference between this one and the jump game is this time we need to count how many step we need to go from the start to the end.

we need to go through the whole array for once. The complexity if O(n).


we need two extra pointers "last" to track last element and count to track how many step we need to go.



code is as follow:

class Solution:
    # @param A, a list of integers
    # @return an integer
    def jump(self, A):
        index=0
        count=0
        last=0
        reach=0
        while reach>=index and index


点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:CodeForces 520C DNA Alignment
下一篇:C. DNA Alignment 数学公式推导 Codeforces Round #295 (Div. 2)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 全峰安全联盟--致力于做实用的IT技术学习网站