LeetCode_55_Jump_Game

LeetCode_55_Jump_Game

群里做题第一天，easy题 55. 跳跃游戏

题目内容是

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

从题目描述就可以看出这是一个简单的模拟题，当然万物皆可模拟。

题解

开一个等长数组用来标记当前位置是否可以达到，然后就是从0开始遍历每个位置从当前位置到该位可以到达的最远距离并且对每个位置赋值，当然这里要进行一个优化判断(对当前位置可到达的最远位置判断是否已经赋值)，不然时间可以达到O(n^2),进行一个剪枝判断后O(2n).

下面贴代码

fun canJump(nums: IntArray): Boolean {
    var dp = arrayOfNulls<Int>(nums.size)
    var max = 0
    dp[0] = 1
    for (i in 0 until nums.size - 1) {
        if (i + nums[i] > max && dp[i] != null) {
            for (j in max..i + nums[i]) {
                if (j > nums.size - 1)
                    return true
                dp[j] = 1
                max = maxOf(j , max)
            }
        }
    }
    return dp[nums.size - 1] != null
}

然后看了下评论后发现倒序可以实现O(n)，果然是思维没打开

    var mStep = 1
    for (i in nums.size - 2 downTo 0) {
        if (nums[i] > mStep) {
            mStep = 1
        } else {
            mStep++
        }
        if (i == 0 && mStep > 1) {
            return false
        }
    }
    return true
}

1557112585(1).png