LeetCode 55. Jump Game (贪心)

短命女 2024-04-18 11:05 58阅读 0赞

题目描述：

这题是上一题（[https://blog.csdn.net/qq\_36652619/article/details/100565302][https_blog.csdn.net_qq_36652619_article_details_100565302]）的弟弟，

每个点的数字代表可以从当前节点跳跃最远的节点数，比如 \[ 2, 3, 1, 1, 4 \] 第一个节点跳跃最远位置就是下标为2的第三个元素。

求是否能到最后一个节点？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

解析：

这个题比上一篇那个简单，不需要实现最少次数，所以其实用贪心算法很快能解决。

贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。

其实就是不断的选择更远的距离，看看距离最终是否能覆盖到最后一个元素

那我们只需要不断地有更远的距离就替换掉我们记录的最远距离值，到最后如果最远距离不能到达最后一个就返回false，能到返回true。

下方代码思路：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

class Solution {
    public:
        bool canJump(vector<int>& nums) {
            //总长度
            int len = nums.size();
            //目前能触及的最远距离
            int theFarthestDistance = 0;
            for(int i = 0; i < len; i++){
                if(i == (len-1)) break;
                //能到达的最远距离的点为0，说明无论如何不能往后延伸，说明不可以
                if(i == theFarthestDistance && nums[i] == 0) return false;
                theFarthestDistance = max((nums[i] + i), theFarthestDistance);
            }
            return true;
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2][]

下方代码思路：

可能下面这种比上面好理解点

![2019090520394658.png][]

class Solution {
    public:
        bool canJump(vector<int>& nums) {
            //总长度
            int len = nums.size();
            //目前能触及的最远距离
            int theFarthestDistance = 0;
            for(int i = 0; i < len; i++){
                //i是最远距离到不了的地方
                if(i > theFarthestDistance) return false;
                theFarthestDistance = max((nums[i] + i), theFarthestDistance);
            }
            return true;
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 3][]

下面的代码少了判断更快，所以还是后面的代码比较好，也容易理解

[https_blog.csdn.net_qq_36652619_article_details_100565302]: https://blog.csdn.net/qq_36652619/article/details/100565302
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1defebd9f5ed4d4bafd9124a789a0027.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c2a60bdb456b41c4884af9414df4fb6a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/74c4506d264e4a8f99e8c27b180a3e24.png
[2019090520394658.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c2e76f8574ba435d956f12454da1bc38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2f4d2c354b2545f79f31588a9903cb46.png