给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。 1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1 2.如果无法跳跃(即数组长度为0),也请返回-1 3.数据保证返回的结果不会超过整形范围,即不会超过 数据范围:-笔试面试资料

这是qklbishe.com第19205 篇笔试面试资料
提供答案分析,通过本文《给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。 1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1 2.如果无法跳跃(即数组长度为0),也请返回-1 3.数据保证返回的结果不会超过整形范围,即不会超过

数据范围:-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。
1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1
2.如果无法跳跃(即数组长度为0),也请返回-1
3.数据保证返回的结果不会超过整形范围,即不会超过给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。    1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1    2.如果无法跳跃(即数组长度为0),也请返回-1    3.数据保证返回的结果不会超过整形范围,即不会超过            数据范围:

数据范围:
给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。    1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1    2.如果无法跳跃(即数组长度为0),也请返回-1    3.数据保证返回的结果不会超过整形范围,即不会超过            数据范围:
给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。    1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1    2.如果无法跳跃(即数组长度为0),也请返回-1    3.数据保证返回的结果不会超过整形范围,即不会超过            数据范围:

Java

给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。    1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1    2.如果无法跳跃(即数组长度为0),也请返回-1    3.数据保证返回的结果不会超过整形范围,即不会超过            数据范围: 零葬

暴力递归

从左往右的尝试模型,到达某个位置cur的时候,有如下情况:
  1. 这个位置刚好到达了数组末尾,说明可以跳到数组的尾端,结算到目前位置的得分,然后更新最大的得分;
  2. 这个位置处于中间位置,如果当前位置nums[cur]=0,不用继续了,当前跳跃方案无效;否则继续递归尝试下一步的跳跃长度[1,nums[cur]]。
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param nums int整型一维数组       * @return int整型      */     int maxScore = -1;     public int maxJumpGrade (int[] nums) {         // write code here         if(nums.length == 0) return -1;         recurrent(nums, 0, 0);         return maxScore;     }          private void recurrent(int[] nums, int cur, int score) {         if(cur >= nums.length - 1){             maxScore = Math.max(maxScore, score + nums[Math.min(nums.length - 1, cur)]);             return;         }         score += nums[cur];         if(nums[cur] != 0){             for(int i = 1; i <= nums[cur]; i++){                 recurrent(nums, cur + i, score);             }         }     } }

 本来按照惯例,我应该表示暴力递归的做法过于暴力,通过不了。但让我意外的情况出现了,提交了一下,暴力递归竟然AC了。尽管如此,抱着端正的学习态度,我也还是会根据暴力递归到动态规划的套路,再改出一版动态规划。

动态规划

构建一个dp数组,其中dp[i]表示从i位置跳跃到末尾的最大得分。由递归的逻辑可以看到,dp[cur]是依赖于后面dp[cur+i]取值的,因此这个动态规划表应该从后往前填。而状态转移只要根据递归的逻辑改就可以了,都是固定套路,没什么难度。
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param nums int整型一维数组       * @return int整型      */     public int maxJumpGrade (int[] nums) {         // write code here         int n = nums.length;         if(n == 0) return -1;         int[] dp = new int[n];         Arrays.fill(dp, -1);         dp[n - 1] = nums[n - 1];         for(int cur = n - 2; cur >= 0; cur--){             if(nums[cur] == 0) continue;             for(int i = 1; i <= nums[cur]; i++){                 if(dp[Math.min(n - 1, cur + i)] != -1){                     dp[cur] = Math.max(dp[cur], nums[cur] + dp[Math.min(n - 1, cur + i)]);                 }             }         }         return dp[0];     } }

2021-12-19 19:43:54 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度,如果可以跳到数组最后一个位置,请你求出跳跃路径中所能获得的最多的积分。 1.如果能够跳到数组最后一个位置,才能计算所获得的积分,否则积分值为-1 2.如果无法跳跃(即数组长度为0),也请返回-1 3.数据保证返回的结果不会超过整形范围,即不会超过 数据范围:-笔试面试资料

提供最优质的资源集合

立即查看 了解详情