本文共 2700 字,大约阅读时间需要 9 分钟。
参考文章
给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以向后跳跃的最大长度。判断你能不能到达数组的最后一个位置。
思路:从数组的第一个位置开始,往后一格一格遍历数组,当所遍历的位置还没超出可reach范围时,根据跳力更新可reach范围,可遍历的范围必须小于等于reach值。若可reach范围可覆盖数组最后一个位置,则可到达;若不可覆盖则不可到达。class Solution1{ public boolean jumpGame(int[] num){ int N=num.length,reach=0; for(int i=0;i<=reach;i++){ if(reach =N-1) return true; } return false; }}
若可以到达数组最后一个位置,求出所用最小步数;若不可到达,返回-1。
思路:参照问题一,只不过在遍历时要更加细化一些,在遍历完x步可到的位置后,和遍历x+1步可到的位置前时,更新步数参数step为x+1。class Solution2{ public int jumpGame(int[] num){ int N=num.length,i = 0,reach=0,step=0,nextReach=0; if(N=1) return 0; while(i<=reach) { for ( ; i <= reach; i++) { if (nextReach < i + num[i]) nextReach = i + num[i]; if (nextReach >= N - 1) return step+1; } reach=nextReach; ++step;//更新step数值后,第step步最远能走到nextReach处 nextReach=0; } return -1; }}
对于数组中的每个位置,到达此位置所需的最小步数是多少。如不可达则为-1。
思路1:参照问题二的解答,每步可达的范围其实已经求出来了。class Solution3{ public int[] jumpGame1(int[] num){ int N=num.length,i=0,j=1,reach=0,step=0,nextReach=0; int[] stepNum=new int[N]; stepNum[0]=0; while(i<=reach) { for ( ; i <= reach; i++) { if (nextReach < i + num[i]) nextReach = i + num[i]; if (nextReach >= N - 1) { for(;j<=N-1;j++){ stepNum[j] =++step; } return stepNum; } } reach=nextReach; ++step; nextReach=0; for(;j<=reach;j++){ stepNum[j] =step; } } for(;j<=N-1;j++){ stepNum[j] =-1; } return stepNum; }}
思路2:一种很糟糕的暴力解答,遍历每个位置,对于每个位置遍历其跳力,让位置步数+1去尝试“松弛”位置加其跳力后对应的位置的最小步数。
class Solution3{ public int[] jumpGame2(int[] num){ int N=num.length,reach=0,nextReach=0; int[] stepNum=new int[N]; for(int i=1;iN-1) return stepNum; if(stepNum[i]+1
很明显,这种糟糕的解法时间复杂度是O(n^2),因为它有很多次无效的尝试松弛的操作,若要在此基础上优化,考虑两点:
对比思想二的那种方法,在一次for循环里面,就是在i+j这个地方将nextReach更新到最大值,到了i+num[i]的地方reach就变成nextReach了,然鹅现在这种方法却是将i变为i+j再往前遍历,光看i它是在跳着走,但遍历它的跳力其实可以看作思想二中的i向前走。于是,思想二中的i是一直向前走,而本方法是走到跳x次能到的最远范围后,再退几步到i+j再往前走。因此考虑第二个改进条件
对于选定的 i(假设属于跳x次能到的范围),在每次加跳力j时,使得 i+j 从跳x+1次的范围起点处开始遍历(也就是说 j 不一定从1开始),那就是线性时间复杂度了。(这样做其实跟前面的解答是一种思想)
如图,红色是更新i后的
class Solution3{ public int[] jumpGame21(int[] num){ int N=num.length,reach=0,reachAgo=0,nextReach=0,nextI=0; int[] stepNum=new int[N]; for(int i=1;iN-1) return stepNum; if(stepNum[i]+1