Nuggets team number online, help you Offer impromptu! Click for details

preface

Today’s brush to the problem is mainly the implementation of greedy algorithm. The so-called greedy algorithm is an algorithm that takes the best or optimal (that is, the most favorable) choice in the current state in every step of the choice and hopes to lead to the best or optimal result. For example, in the traveling salesman problem, if the traveler chooses the nearest city every time, this is a greedy algorithm.

Topic describes

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

Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

The most typical way to do this is to use the greedy strategy, for the leg, we can first draw a conclusion: assume the current jump to the I coordinate. So all the coordinates before I must be reachable. So we just need to maintain the maximum distance that we can jump to for each element of the array. So for the i-1 element, the farthest he can go is i-1+num[i-1]. Assume that the maximum jump distance we maintain at this point is K. So, then the maximum distance you can jump to at this point is Max (i-1+num[i-1],k) (because i-1 may have reached a greater distance k before him). And we’re going to maintain this maximum into k, and we’re just going to compare k and I, based on what we just learned.

Other solutions

I looked at other solutions in LeetCode, and some of them used backtracking. The general idea is to start with the end point (the final position) and backtrack. For any point I, we can traverse point J in [0,i-1]. If nums[j] >= i-j, then we can reach point J from point I, and further investigate whether j can be reached by points in [0,j-1]. If an unreachable point occurs halfway through, go back to the point in the previous layer (closer to the end point).

class Solution {
public:
    // Essentially DFS: probe backtracking
    bool trace_back(vector<int> & nums, int target)
    {   // Determine whether to reach target from SRC
        if (target==0)
            return true;/ / recursive matrix

        for (int src = target- 1; src >= 0; src--)
        {
            if (nums[src] >= target - src)
                return trace_back(nums, src);// Continue along the SRC path
        }

        return false;
    }

    bool canJump(vector<int>& nums) {
        int target = nums.size(a)- 1;
        
        return trace_back(nums, target); }};Copy the code

DFS Solution from author: zongy17 Link: leetcode-cn.com/problems/ju…

The final code

class Solution {
    public boolean canJump(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > k) return false;
            k = Math.max(k, i + nums[i]);
        }
        return true; }}Copy the code

conclusion

Although the efficiency of DFS is not ideal, it is still an idea worth learning. This article is participating in “Digging gold in April 2021 swipe card”, click to see the activity details. Give it a thumbs up if you like.