LeetCode T45 跳跃游戏II
题目链接:45. 跳跃游戏 II - 力扣(LeetCode)
题目思路:
这题我们仍然使用贪心的思路来解决问题,我们仍然是判断每次能跳的最大步数来达到用最少的步数到达终点,这题我们仍然采用覆盖的思想,我们采用一个cur记录下目前的最大覆盖,采用一个next记录下次跳到哪个位置(在覆盖中更新以得到最大距离),一个result记录步数,只要cur没走到终点后面,我进行更新cur的时候就算走了一步,如果到终点或者超越终点了,就跳出循环,直接返回目前记录的步数即可
题目代码:
class Solution { public int jump(int[] nums) { int result = 0; int next = 0; int cur = 0; for(int i = 0;i<nums.length;i++) { next = Math.max(i+nums[i],next); if(i == cur) { if(cur<nums.length-1) { result++; cur = next; } else { break; } } } return result; } }