贪心算法的实现和特性

贪心算法 Greedy。

贪心算法是一种在每一步选择中都采取在当前状态下最好或者最优选择，从而希望达到整体最优。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。
动态规划 则会保存之前的运算结果，并根据之前的结果对当前结果进行选择，有回退功能。

贪心：局部最优判断
回溯：能够回退
动态规划：最优判断 + 回退

贪心算法可以解决一些最优化处理，如：求图中的最小生成树、求哈夫曼编码等。
对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。

一旦一个问题可以通过贪心算法解决，那么贪心算法一般是解决这个问题的最好办法。贪心算法由于其高效性以及其所求得的答案比较接近最优解，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

适用于贪心算法的场景：

简单概括，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。

coin change 题目

// coin change
// 思路：动态规划

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
  if (!amount) return 0;

  const dp = new Array(amount + 1).fill(Infinity);

  dp[0] = 0;

  for (let i = 0; i < coins.length; i++) {
    for (let j = coins[i]; j <= amount; j++) {
      dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
    }
  }

  return dp[amount] = Infinity ? -1: dp[amount];
};

柠檬水找零（亚马逊在半年内面试中考过）

买卖股票的最佳时机 II （亚马逊、字节跳动、微软在半年内面试中考过）

分发饼干（亚马逊在半年内面试中考过）

跳跃游戏 （亚马逊、华为、Facebook 在半年内面试中考过）

跳跃游戏 II （亚马逊、华为、字节跳动在半年内面试中考过）

// 柠檬水找零
// (●'◡'●) 没错，就是官方题解，没有更简单方法

var lemonadeChange = function(bills) {
  let five = 0,
      ten = 0;

  for (const bill of bills) {
    if (bill === 5) {
      five += 1;
    } else if (bill === 10) {
      if (five === 0) {
        return false;
      }
      five -= 1;
      ten += 1;
    } else {
      if (five > 0 && ten > 0) {
        five -= 1;
        ten -= 1;
      } else if (five >= 3) {
        five -= 3;
      } else {
        return false;
      }
    }
  }

  return true;
};

// 买卖股票的最佳时机 II

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  let sum = 0;

  for (let i = 0; i < prices.length; i++) {
    const num = prices[i + 1] - prices[i];

    num > 0 && (sum += num);
  }

  return sum;
};

// 分发饼干问题

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
  const sortFn = (a, b) => a - b;

  g.sort(sortFn);
  s.sort(sortFn);

  let count = 0;

  s.forEach(item => {
    if (item >= g[count]) {
      count++;
    }
  });

  return count;
};

// 跳跃游戏

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
  if (!nums) return false;

  let endReachable = nums.length - 1;

  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] + i >= endReachable) {
      endReachable = i;
    }
  }

  return endReachable === 0;
};

// 跳跃游戏 II

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
  let farthest = 0,
      curr = 0;

  let steps = 0;

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, nums[i] + i);

    if (curr == i) {
      curr = farthest;
      steps++;
    }
  }

  return steps;
};