leetcode 55. Jump Game 跳跃游戏 + 贪心算法

小灰灰 2022-06-09 10:53 197阅读 0赞

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.

这道题和上一道题[ leetcode 45. Jump Game II 贪心算法&&DFS深度优先搜索][leetcode 45. Jump Game II _DFS] 一模一样，不过这次改成了判断题，这里就不说了，直接上代码。

代码如下：

public class Solution 
    {
        /*
         * 下面是使用贪心算法解决，
         *  主要的问题是假如无法达到终点，这种情况应该怎么发现和处理
         * */
        public boolean canJump(int[] nums) 
        {
            if(nums==null || nums.length<=0 || nums.length==1 && nums[0]>=0)
                return true;
    
            int i=0;
            while(i<nums.length-1)
            {   
                if(i+nums[i]>=nums.length-1)
                    return true;
                else
                {
                    //由于是贪心算法，当前的最大跳跃步数为0的时候就表明无法到达终点
                    if(nums[i]==0)
                        return false;
    
                    int maxLen=0;
                    int index=0;
                    for(int j=1;j<=nums[i];j++)
                    {
                        if(j+nums[i+j]>maxLen)
                        {
                            maxLen=j+nums[i+j];
                            index=i+j;
                        }
                    }
                    i=index;
                }       
            }
            return false;
        }
    }

下面是C++的做法，就是一个贪心算法的经典应用，很值得学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        bool canJump(vector<int>& a) 
        {
            if (a.size() <= 1)
                return true;
            int i = 0;
            while (i < a.size())
            {
                if (i + a[i] >= a.size() - 1)
                    return true;
                else
                {
                    if (a[i] == 0)
                        return false;
                    int index, maxLen = 0;
                    int size = a[i];
                    for (int j = 1; j <= size && j + i < a.size(); j++)
                    {
                        if (j + a[i + j] > maxLen)
                        {
                            maxLen = j + a[i + j];
                            index = i + j;
                        }
                    }
                    i = index;
                }
            }
            return false;
        }
    };

[leetcode 45. Jump Game II _DFS]: http://blog.csdn.net/jackzhang_123/article/details/77823076