牛客NC197 跳跃游戏(一)【中等 动态规划 Java、Go、PHP】

题目

题目链接：
https://www.nowcoder.com/practice/23407eccb76447038d7c0f568370c1bd

思路

答案说的merge区间就是每个A[i]的地方能跳到的最远坐标是A[i] + [i]，
有一个maxReach，遍历一遍A[i], 不断刷新MaxReach, 如果某个i 位置比maxReach要大，
则说明这点跳不过去， return false，否则的话这点可以跳过去，
只要能遍历完就可以return true了

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return bool布尔型
     */
    public boolean canJump (int[] nums) {
        //DP
        /*
         答案说的merge区间就是每个A[i]的地方能跳到的最远坐标是A[i] + [i]，
         有一个maxReach，遍历一遍A[i], 不断刷新MaxReach, 如果某个i 位置比maxReach要大，
         则说明这点跳不过去， return false，否则的话这点可以跳过去，
         只要能遍历完就可以return true了
         */
        int maxReach = nums[0];
        for (int i = 1; i < nums.length ; i++) {
            if (i <= maxReach) {
                maxReach = Math.max(maxReach, nums[i] + i);
            } else {
                return false;
            }
        }
        return true;
    }
}

参考答案Go

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return bool布尔型
 */
func canJump(nums []int) bool {
//DP
/*
   答案说的merge区间就是每个A[i]的地方能跳到的最远坐标是A[i] + [i]，
   有一个maxReach，遍历一遍A[i], 不断刷新MaxReach, 如果某个i 位置比maxReach要大，
   则说明这点跳不过去， return false，否则的话这点可以跳过去，
   只要能遍历完就可以return true了
*/
maxReach := nums[0]
for i := 1; i < len(nums); i++ {
if i <= maxReach {
cur := nums[i] + i
if cur >= maxReach {
maxReach = cur
}
} else {
return false
}
}
return true
}

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return bool布尔型
 */
function canJump( $nums )
{
   
    //DP
    /*
       答案说的merge区间就是每个A[i]的地方能跳到的最远坐标是A[i] + [i]，
       有一个maxReach，遍历一遍A[i], 不断刷新MaxReach, 如果某个i 位置比maxReach要大，
       则说明这点跳不过去， return false，否则的话这点可以跳过去，
       只要能遍历完就可以return true了
    */
    $maxReach = $nums[0];
    for($i=1;$i<count($nums);$i++){
        if($i<=$maxReach){
            $cur = $nums[$i]+$i;
            if($cur>$maxReach){
                $maxReach = $cur;
            }
        }else{
            return false;
        }
    }
    return true;
}

原文地址：https://blog.csdn.net/weixin_37991016/article/details/137889969

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！