This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Jumping games

Given an array of non-negative integers, nums, you start at the first index of the array. Each element in the array represents the maximum length you can jump at that location. Determine if you can reach the last index.

Example 1:

Input: nums = [2,3,1,1,4] output: trueCopy the code

Example 2:

Input: nums = [3,2,1,0,4] Output: false But this subscript has a maximum jump length of 0, so you can never reach the last subscript.Copy the code

Tip:

  • 1 <= nums.length <= 3 * 104
  • 0 <= nums[i] <= 105

Thought analysis

A greedy algorithm can be used to iterate through each position in the array and maintain the farthest reachable position in real time. If the last position cannot be reached by the end of the loop, return false.

Another solution is to iterate from the tail, maintaining a value of n that defaults to 1, adding up if the value at that position is less than n, or resetting to 1 until the end.

The time complexity of this method is O(n){O(n)}O(n), and the space complexity is O(1){O(1)}O(1).

The code shown

Solution 1: greedy algorithm, real-time maintenance of a farthest reachable location.

			public boolean canJump(int[] nums) {        
				int max = 0;
        int length = nums.length;
        for(int i = 0; i < length; ++i){if(length == 1 && (nums[0] = =0)) {return true;
            }
            if(max < i){
                return false;
            }
            max = Math.max(max,i+nums[i]); / / 3,2,1,0,4
        }
        return true;
Copy the code

Solution 2: Start from the tail to traverse

    public boolean canJump(int[] nums) {
        int n = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] >= n) {
                n = 1;
            } else {
                n++;
            }
            if (i == 0 && n > 1) {
                return false; }}return true;
Copy the code

conclusion

This problem can be solved using greedy and tail-beginning traversal with time complexity O(n){O(n)}O(n) and space complexity O(1){O(1)}O(1). You can also use DFS and dynamic programming.