欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 国际 > Java面试经典 150 题.P55. 跳跃游戏(009)

Java面试经典 150 题.P55. 跳跃游戏(009)

2024/11/5 13:31:39 来源:https://blog.csdn.net/qq_61942909/article/details/143371309  浏览:    关键词:Java面试经典 150 题.P55. 跳跃游戏(009)

本题来自:力扣-面试经典 150 题

面试经典 150 题 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台icon-default.png?t=O83Ahttps://leetcode.cn/studyplan/top-interview-150/

题解:

class Solution {public boolean canJump(int[] nums) {int len = nums.length;int i = len - 2;int tar = len - 1;for(;i >= 0;i--){if(nums[i] + i >= tar)tar = i;}if(tar == 0)return true;return false;}
}

思路如下:

使用逆向思维+贪心算法,虽然题上没有说只能向右跳,但是思考一下向左跳是没有意义的,因为

题目只要求我们求出是否可以到达,回跳只会增加到达的可能路径,并不会把到不了变成能到

其次,数组的最后一位是没有意义的,因为他是终点

分析完成,现在需要做的就是判断如何到达,如果从起点开始的话,要考虑的太多了,因为我们不知道要跳几步,但是如果从终点反向推到,就可以只是用最大跳跃距离,也就能使用贪心算法

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com