lc:45贪心

贪心算法

第45题

给一个数组，从头跳到尾，数组内的值代表当前能跳的步数。

const jump = function(nums) {    let maxPosition = 0;    // 未到边界前，下一步能到的最远位置  let end = 0;  // 当前能跳的边界    let steps = 0;    for(let i=0; i<nums.length-1; i++) {    maxPosition = Math.max(maxPosition, i+nums[i]);    if(i===end) {               end = maxPosition;  // 到边界后，更新下一步的边界为能跳到的最远位置      steps += 1;    }  }  return steps;}

每次都跳能跳的最远位置，贪心算法，一直到最后。

这里有一处巧妙的地方，for循环中的判断条件，是小于nums.length-1的,也就是说i是永远到不了数组中最后那个位置的，而最后一次的end必然会大于等于数组最后的位置，所以step就少一次增加。因为在太初之时，盘古开天辟地的时候，我们给end赋值为0，也就是说第一次刚进入程序执行的时候step就已经加一了，这里需要注意一哈。

---

2020.6.19
written by Rain.