时隔一周,终于又开始写leetcode的每日一题系列了,其实之前还有一篇推荐软件的文章,但是因为还没来得及写完就暂时先隐藏了。

其实说实话,最近的时间一直都比较紧张,想要保持博客的更新也比较困难,基本上早上起床到晚上八点多一直在公司工作,也不太好写文章,晚上电脑也不好总是带回来,时间本来也已经很晚了。好了,话不多说,看一下今天的题目吧。

55.跳跃游戏🤡

这道题被 leetcode官方定为难度中等,但是通过率却也只有可怜的4成左右,题目描述如下:

题目描述

给定一个非负整数数组,你最初位于数组的第一个位置
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

  • 示例:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳一步,从位置0到达位置1,然后再从位置一跳3步到达最后一个位置。

思路解析

说实话一开始看到这个问题的时候我想麻烦了,可能是被这个示例给诱导了,所以第一感觉是从前往后跳的话策略实在是太多了,所以一开始我的思路是反推,从后向前,比如以最后一个目标点为基准向前推进,选出所有可以一次性到达这个位置的点,然后再对这些点的集合继续执行这个操作。其中当某一轮所有可达的点的集合中包含位置0时就表示可达,而再无法找到一个点可以抵达的时候就表示不可达。但后来我发现初始的数组不算大的时候,这个方法就开始需要消耗极多的资源,同时还会存在许多重复计算的点,着实是不太适合。(当然如果加上一个缓存来存储已经计算过的点的话,可以减少很多不必要的计算,应该可以通过。)

然后我重新审视了一次题目,当我发现你可以在每个位置跳1~N步的时候,我突然发现了问题所在,我们根本不需要计算是否能抵达某个点,我们只需要计算从出发点开始最远可以走到哪里,如果最远的距离超过了重点的距离,那么久一定可以跳到终点去。有了这个思路我又开始写代码:

import kotlin.math.max

class JumpGame{
    fun canJump(nums:IntArray):Boolean{
        //先设置最远可达距离为0,因为这个数每轮都有可能会变化,所以设置为var
        var furthest = 0
        for(i in 0 until nums.size){
            if(i <= furthest){
                //这里的 i <= furthest 意思就是当前准备遍历的点在最远可达范围之内,如果连当前点都无法到达,就更不用提到达终点了。
                //取当前点能够到达的最远位置(i+nums[i])和furthest比较,取其中较大值
                furthest = max(furthest, i+nums[i])
                if(furthest >= n-1){
                    //如果最远可达位置大于等于终点所在的位置时,即可证明可达终点,直接返回true
                    return true
                }
            }
        }
        //循环遍历完成之后如果程序还未结束,那就证明已经无法抵达终点了,所以返回false
        return false
    }
}

这个方法算是比较简单容易理解的一种方法,代码也很简单明了容易理解,而在完成了这个之后,我查看了官方的和精选的题解,挑了一些查看。也发现了不少很有深度的解答,提到了许多知识点,大家也都可以去题解区多看看大神的解答,或许会给自己带来一些意想不到的收获。

好了,今天的每日一题暂时就到这里了,我们有缘再会。(我也只能给自己找理由说是工作忙了。)