算法记录
LeetCode 题目:
给你一个非负整数数组 nums ,你最初位于数组的第一个位置。
思路
说明
一、题目
数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
二、分析
- 就是判断当前点到移动最大距离之间有没有更远的范围可以选择, 有的话下一跳就在那里, 没有直接到按照当前点的最大值跳.
- 和操作系统的资源预先分配类似, 要知道当前点的决策是不是最优的.
class Solution {
public int jump(int[] nums) {
if(nums.length == 1) return 0;
int ans = 1, pre = 0, pos = nums[0];
while(pos < nums.length - 1) {
int temp = 0;
for(int i = pre; i <= pos; i++) {
temp = Math.max(temp, nums[i] + i);
}
pre = pos;
pos = temp;
ans++;
}
return ans;
}
}
总结
熟脑筋急转弯。