郑州做网站首选九零后网络,长沙有哪些网站建设公司,湘潭做网站 m磐石网络,做优化送网站给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处:
0 j nums[i] i j n
返回到达 nums[n - 1] 的最…给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处:
0 j nums[i] i j n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 示例 1:
输入: nums [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是2。
从下标为 0 跳到下标为 1 的位置跳1步然后跳3步到达数组的最后一个位置。示例 2:
输入: nums [2,3,0,1,4]
输出: 2提示:
1 nums.length 0 nums[i] 1000题目保证可以到达 nums[n-1] 分解题目
目标求解跳到最后一个位置的最小跳跃数依赖于存在一个位置能跳到最后一个位置题目已经保证此项 跳到这个位置的最小跳跃数。如果用 i 来表示最后一次跳跃i - 1表示的倒数第二次跳跃很明显求解 i 的最小跳跃数可以转换为求解 i - 1的最小跳跃数。 至此可以用动态规划进行解决。 定义dp[ i ]表示跳跃到第 i 个位置的最小跳跃数。dp[n - 1]即为所求边界值dp[0] 0。
对于第 i 个位置可能有多个前置的位置可以跳跃到达我们需要找到其中的最小值即
j from 0 to i
if(nums[j]ji) dp[i]min(dp[i],dp[j]1);
完整代码
class Solution {
public:int jump(vectorint nums) {int n nums.size();vectorint dp(n,n);dp[0] 0;for(int i 1;i n;i){for(int j 0; j i;j){if(nums[j] j i){dp[i] min(dp[i],dp[j] 1);}} }return dp[n-1];}
}; 然而这里的动态规划反而引入了更多的重复计算。 如果换成贪心算法
class Solution {
public:int jump(vectorint nums) {int jumps 0;int end 0;int farthest 0;for (int i 0; i nums.size() - 1; i) {farthest max(farthest, nums[i] i);if (i end) {jumps;end farthest;if (end nums.size() - 1) {break;}}}return jumps;}
};
jumps是跳跃的次数end是当前的终点farthest是当前点跳跃能够到达的最远点。遍历数组除了最后一个元素因为最后一个元素的位置不需要跳跃自己就能到达自己。我们时刻维护从当前点到达的最远距离当我们到达了当前终点就把最远距离设置成终点这里体现贪心的思想。同时当到达了end时也说明需要进行一次跳跃。
即每次在上次能跳到的范围iend内选择一个能跳的最远的位置也就是能跳到farthest位置的点作为下次的起跳点。 对于初学者这看上去非常的反直觉这是不是局部最优为什么是全局最优如果出现当前跳的最远但是下下步跳得近了怎么办 这里需要理解end的作用如果把end抽象成一个分隔符所谓跳跃过程就是在数组内插入分隔符的过程使最终分出的子数组数量最小。
而fareset的作用是保留上一个end到当前end这个区间范围内可以达到的最远值。
注意区间范围这个点。 在贪心算法中每一步的end都是当前范围能到达的最远点也即最大值farest所以最终分出的间隔就会更少。 下面用一个具体图例做进一步解释初始状态进行第一次跳跃 跳跃后在区间内遍历维护最远值farest 这里有人可能会说看起来像恰好1就跳到了较大值10。那如果我们把这里的1换成0会发生什么 可以看到维护的farest才是起到关键作用的值。和nums[end]中的值并无全部关系。 这也是上面提到的保留上一个end到当前end这个区间范围内可以达到的最远值。
图中箭头描述的是end变化的过程真实的跳跃过程和end的变化过程数量相同但是路径不一定相同。每条end箭头仅对应一条跳跃比如这里是从2跳到3跳到10。
继续遍历 只要理解了end表示间隔且和真实跳跃一一对应farest表示一个区间内跳到的最远距离这两个概念这里的贪心算法就很好理解了。
