学好算法没有捷径,最好的捷径就是多刷题,并且跳出舒适区,每道题都要寻找最优解,也不能老是做那些你自己比较擅长的题,不定期更新Leetcode的题,每道题都会给出多种解法以及最优解。
题目描述
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是2。从下标为 0 跳到下标为1的位置,跳1步,然后跳3步到达数组的最后一个位置。
说明:假设你总是可以到达数组的最后一个位置。
方法一、从右往左搜索
我们的目的是要跳跃到最后一个点上,我们可以从最后一个点往左开始寻找,例如非负数组为arr={2,3,1,1,4,2,1},从最右边的1往左寻找,找那个离右边的点最远,却又能到达它的点,如下图:
寻找每一个点的过程中,我们每次都需要遍历一遍数组,看看哪一个点更加合适,所以需要两层循环,时间复杂度为O(n^2),空间复杂度为O(1)。代码如下
public int jump(int[] nums){ int right = nums.length - 1; int sum = 0; while(right > 0){ // 寻找离 last 最远,且能够到达 last 的点 int cur = right - 1; for(int i = right - 2; i >= 0; i--){ // 是否能够达到 last 这个点 if( i + nums[i] >= right){ cur = i; } } right = cur; sum++; } return sum; }方法二:贪心算法
这道题的最优解是可以时间复杂度优化到O(n)的,那就是采用贪心算法,我们从左边的起点开始跳跃的时候,我们应该跳跃到哪一个点比较合适呢?,显然,每次都跳跃最大长度的话,是不行的。例如对于上面arr={2,3,1,1,4,2,1}这个例子,刚开arr[0]=2,那么我们可以跳到arr[1]=3或者arr[2]=1上,显然,我们跳跃arr[1]=3会更好一点。如图(图片来源于网络)
接着同样的道理,我们可以从arr[1]=3这个位置开始跳跃,它可以跳跃到arr[2]=1,arr[3]=1,arr[4]=4这三个位置,显然,我们跳到arr[4]=4这个位置好一点,如图(图片来源于网络)
也就是说,我们要跳跃的那个点,可以使得上一次+下一次的跳跃总距离最远。代码如下
public int jump(int[] nums) { if(nums.length < 2) return 0; int sum = 0; int end = 0; // 能跳到的最远距离 int max = 0; // 下一步可以跳到的最远距离 for(int i = 0; i < nums.length - 1; i++){ max = Math.max(max, i + nums[i]); // 更新当前点 if(i == end){ end = max; sum++; } } return sum; }
时间复杂度是O(n),空间复杂度是O(1)。
推荐阅读: