大家好，今天来为大家解答游戏网站程序源码分享这个问题的一些问题点，包括游戏网页源码也一样很多人还不知道，因此呢，今天就来为大家分析分析，现在让我们一起来看看吧！如果解决了您的问题，还望您关注下本站哦，谢谢~
问题陈述
给定一个非负整数数组nums，您最初位于数组的第一个索引处。
数组中的每个元素代表您在该位置的最大跳跃长度。
您的目标是以最少的跳跃次数达到最后一个索引。
您可以假设您始终可以到达最后一个索引。
示例1：
Input:nums=[2,3,1,1,4]\nOutput:2\nExplanation:Theminimumnumberofjumpstoreachthelastindexis2.Jump1stepfromindex0to1,then3stepstothelastindex.
示例2：
Input:nums=[2,3,0,1,4]\nOutput:2
约束:
-1<=nums.length<=10^4\n-0<=nums[i]<=1000
解释
问题是我们之前博客文章JumpGame的扩展。在JumpGame问题中，我们必须计算是否可以到达数组的最后一个索引。在这个问题中，我们需要计算最小的跳跃次数。
蛮力方法
天真的方法是使用递归来解决问题。当我们到达最后一个索引时，将发生此递归中的基本情况。
我们将递归调用从第一个元素可到达的所有元素。这意味着我们将探索递归堆栈中的所有分支，并返回到达最后一个索引的最小跳转次数。
这种方法的C++片段如下：
intminJumps(vector<int>&nums,intindex){\nif(index>=nums.size()-1)\nreturn0;intjumps=INT_MAX;for(intindex=index+1;i<=index+nums[index];i++)\njumps=min(jumps,1+minJumps(nums,i));returnjumps;\n}
上述方法的时间复杂度为O(2^N)，空间复杂度为O(1)。
动态规划
使用动态规划，我们可以将时间复杂度降低到O(N2)。天真的方法有重叠的子问题，它们的结果存储在一个数组中。在计算节点的最小跳转时，我们检查结果是否存在于存储的数组中。
这种方法的C++片段如下：
intjump(vector<int>&nums){\nintn=nums.size();\nvector<int>store(n);\nstore[0]=0;for(inti=1;i<n;i++){\nstore[i]=INT_MAX;for(intj=0;j<i;j++){\nif(i<=nums[j]+j&&store[j]!=INT_MAX){\nstore[i]=min(store[i],store[j]+1);\nbreak;\n}\n}\n}returnstore[n-1];\n}
上述方法的时间复杂度为O(N2)，空间复杂度为O(n)。
最优贪心方法
在这种方法中，我们使用了一种贪心算法，该算法在每一步都做出最优选择。在任何索引处，我们都会确定使我们接近最后一个索引的下一步。
让我们先检查一下算法。
-setcount,current,farthest=0,0,0-ifnums[0]==0||nums.length==1\n-return0-loopfori=0;i<nums.length;i++\n-ifnums[i]+i>farthest\n-setfarthest=nums[i]+i-ifi==current\n-incrementcount:count++\n-current=farthest-forend-returncount
让我们检查一下我们用C++、Golang和Javascript编写的解决方案。
C++解决方案
classSolution{\npublic:\nintjump(vector<int>&nums){\nintcount=0,current=0,farthest=0;if(nums[0]==0||nums.size()==1){\nreturn0;\n}for(inti=0;i<nums.size()-1;i++){\nif(nums[i]+i>farthest){\nfarthest=nums[i]+i;\n}if(i==current){\ncount++;\ncurrent=farthest;\n}\n}returncount;\n}\n};
Golang解决方案
funcjump(nums[]int)int{\ncount,current,farthest:=0,0,0ifnums[0]==0||len(nums)==1{\nreturn0\n}fori:=0;i<len(nums)-1;i++{\nifnums[i]+i>farthest{\nfarthest=nums[i]+i\n}ifi==current{\ncount++\ncurrent=farthest\n}\n}returncount\n}
Javascript解决方案
varjump=function(nums){\nletcount=0,current=0,farthest=0;if(nums[0]==0||nums.length==1){\nreturn0;\n}for(leti=0;i<nums.length-1;i++){\nif(nums[i]+i>farthest){\nfarthest=nums[i]+i;\n}if(i==current){\ncount++;\ncurrent=farthest;\n}\n}returncount;\n};
让我们针对给定的输入试运行我们的算法。
Input:nums=[2,3,1,1,4]Step1:count=0\ncurrent=0\nfarthest=0Step2:ifnums[0]==0||nums.length==1\n2==0||5==1\nfalseStep3:loopfori=0;i<nums.length-1;i++\ni<nums.length-1\n0<5-1\n0<4\ntrueifnums[i]+i>farthest\nnums[0]+0>0\n2+0>0\ntruefarthest=nums[i]+i\n=2ifi==current\n0==0\ntruecount++\ncount=1current=farthest\n=2i++\ni=1Step4:loopfori<nums.length-1\ni<nums.length-1\n1<5-1\n1<4\ntrueifnums[i]+i>farthest\nnums[1]+1>2\n3+1>2\ntruefarthest=nums[i]+i\n=4ifi==current\n1==2\nfalsei++\ni=2Step5:loopfori<nums.length-1\ni<nums.length-1\n2<5-1\n2<4\ntrueifnums[i]+i>farthest\nnums[2]+2>4\n1+2>4\nfalseifi==current\n2==2\ntruecount++\ncount=2current=farthest\n=4i++\ni=3Step6:loopfori<nums.length-1\ni<nums.length-1\n3<5-1\n3<4\ntrueifnums[i]+i>farthest\nnums[3]+3>4\n1+1>4\nfalseifi==current\n3==4\nfalsei++\ni=4Step7:loopfori<nums.length-1\ni<nums.length-1\n4<5-1\n4<4\nfalseStep8:returncountWereturntheansweras2.
关注七爪网，获取更多APP/小程序/网站源码资源！
文章分享结束，游戏网站程序源码分享和游戏网页源码的答案你都知道了吗？欢迎再次光临本站哦！