Algorithm---Jumping Game (Kotlin)

题目

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 .

数组中的每个元素代表你在该位置可以跳跃的最大长度.

判断你是否能够到达最后一个下标.

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标.
示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样,总会到达下标为 3 的位置.但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标.

提示：

1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game
著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处.

解决思路

方法一：定义一个数组,dp[i]Indicates whether it is possible to jump toi的位置,We just need to start with the array,If the current location can jump to,Then set the interval from the current bit to the jump totrue,If the last bit of the array is true,That means it can be achieved

方法二：The array of the first method can be removed 从第一个位置开始,Directly record a farthest position,within this furthest location,All positions can be adjusted.We make the furthest update on this basis

解决方法

方法一：

    fun canJump(nums: IntArray): Boolean {
    
        val dp = Array(nums.size) {
     false }
        dp[0] = true
        nums.forEachIndexed {
     index, i ->
            if (dp[index]) {
    
                Arrays.fill(dp,index,(index + i + 1).coerceAtMost(nums.size),true)
            }
        }
        return dp[nums.size - 1]
    }

方法二
优化版本：

    fun canJump3(nums: IntArray): Boolean {
    
        var maxRight = nums[0]
        nums.forEachIndexed {
     index, i ->
            if (index <= maxRight){
    
                maxRight = maxRight.coerceAtLeast(index + i)
            }
        }
        return maxRight >= nums.size - 1
    }

总结

1.属于贪心算法,Try to get the maximum value at each step,Use brute force solutions,well written too,That is when the array is too large,效率太低,过不了.
2.Algorithms are the use of time and space,The first method might be fine,But unnecessary space is wasted.