跳跃游戏-算法

题目

给定一个数组nums = {1,2,3,4,5}，每个元素nums[i]表示从i这个位置最多可以向前跳跃nums[i]个台阶，求最小需要跳几次就可以调到末尾

思路

反向查找

从末尾开始逐个向前判断最远的起跳位置，接着再以该位置递归的判断

public int jumpToTheEndWithMinSteps(int[] nums){int position = nums.length-1;int steps = 0;while(position>0){for(int i=0;i<position;i++){if(i+nums[i]>=position){position = i;steps++;break;            }        }    }return steps;
}

效果

时间复杂度：O(n^2)

空间复杂度：O(1)

正向查找

从i=0位置开始向后找，每次在当前最远位置如i，计算从i开始跳跃空间nums[i]内这个区间内能够跳的最远位置是哪里，然后以此类推

public int jumpToTheEndWithMinSteps(int[] nums){int length = nums.length;int end = 0;int maxPosition = 0;int steps = 0;for(int i=0;i<length;i++){//计算i<j<=end区间内能够跳的最远的位置，将其记录为maxPositionmaxPosition = Math.max(maxPosition,i+nums[i]);//每次区间结束，都更新一下最新调的最远的位置if(i==end){end = maxPosition;steps++;        }    }return steps;
}

效果

时间复杂度：O(n)

空间复杂度：O(1)