Jump Game

Jump Game

今天是一道有关贪婪算法的题目，来自LeetCode#55，难度为Medium，Acceptance为27.2%。

题目如下

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.

思路如下

该题中只需要求能不能到达最后一个元素，而不必求最少的步数，相对较为简单。只要按照贪婪算法，每到下一个元素求由该元素开始的最远的元素i + nums[i]即可。

代码如下

java版

public class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for(int i = 0; i <= reach && reach < nums.length; i++) {
            reach = Math.max(reach, i + nums[i]);
        }
        return reach >= nums.length - 1;
    }
}

C++版

bool canJump(int A[], int n) {
    int i = 0;
    for (int reach = 0; i < n && i <= reach; ++i)
        reach = max(i + A[i], reach);
    return i == n;
}

关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助

image