leetcode-jump-game

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/jump-game/

　　给你一个数组，数组上每一个位置上的值代表从当前位置可以往后跳多远，求从数组起点是否能跳跃到数组终点。

题目分析

　　贪心法，从前向后扫描，不断更新最远能跳跃到的位置，如果大于数组末尾那么就返回true.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int maxLoc = 0;
        for(int i = 0; i <= Math.min(len - 1, maxLoc); i++) {// 注意这里i不能超过len - 1
            maxLoc = Math.max(nums[i] + i, maxLoc);
            if (maxLoc >= len - 1) {
                return true;
            }
        }
        return false;
    }
}

　　时间复杂度 O(n)