贪心算法

概念

贪心算法相比动态规划，是在子问题中每次做出局部最优选择，以得到全局最优解。贪心算法不一定总能得到最优解，但对某些问题很有效。
与动态规划不同之处在于，动态规划每次做出的选择依赖于子问题的解，通常需要从较小子问题向较大子问题自底向上求解。而贪心算法不依赖于将来的选择或者子问题的解，而是做出看起来最佳的选择，通常是自顶向下的。
贪心算法的关键是找出最优子结构里的最佳解，并证明该解是最优解。

134.Gas Station
一辆车（假设瓦斯箱容量无限大），有N个瓦斯站，每站存储瓦斯量gas[i]，到下一站消耗瓦斯cost[i]，找出能使车行驶一圈的起点站，若有解则唯一，若无解返回-1。

这道题的子结构为从i站到j站，若i站能到达j站但不能到达j+1站则说明i至j站中任一站不能到达j+1站。证明：

对于任意$$i \le l \le j-1$$

故对于$$i \lt l \le j-1$$

因此我们累加瓦斯的存储量与消耗量，若不能到达某一站，则其中任一站都不是解，从下一站开始累加；最后将得到的所有的油量与消耗量比较来判断是否有解，若有解则一定是最后一个起点。

这道题的贪心在于将子结构里的非解“贪心”的排除掉。

var canCompleteCircuit = function (gas, cost) {
  var totalGas = 0, totalCost = 0;
  var tmp = 0, start = 0;
  for (var i = 0; i < gas.length; i++) {
    totalGas += gas[i];
    totalCost += cost[i];
    tmp += gas[i] - cost[i];
    if (tmp < 0) {
      tmp = 0;
      start = i + 1;
    }
  }
  return totalGas >= totalCost ? start : -1;
};

135.Candy
按照小孩的权重值ratings[i]分糖果，每人至少1个糖果，求要分的最小糖果数。

分析：先将所有糖果设为1，贪心的地方在于先遇到升序直接分1——N（升序长度）的糖果，然后再从后往前从每个升序的起点设置为Max(前一个值加1，当前值）。为什么能这么做是因为糖果只能分整数个，我们能够直接从定义得到答案，从1开始逐1增加必然是最少糖果数。

var candy = function (ratings) {
  var len = ratings.length;
  var candies = new Array(len).fill(1);
  for (var i = 1; i < len; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }
  for (i = len - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i + 1] + 1, candies[i]);
    }
  }
  return candies.reduce(function (val1, val2) {
    return val1 + val2;
  });
};

321.Create Maximum Number
输入两个数组nums1、nums2和数量k，数组每个数范围0-9，返回k个数组中的最大值，要求返回的数组中数的顺序与nums1、nums2不能错位。
Input: nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3] ,k = 5
Output: [9, 8, 6, 5, 3]

分析：输出的数组前面位数一定要尽可能最大。一开始想依次求两个数组中剩余数的最大值，但是这样与给出的k会矛盾。看了下论坛答案，可以从两个数组中依次挑出较大的长度为i和k-i的数组来进行组合，每次进行比较即可。

var maxNumber = function (nums1, nums2, k) {
  var res = new Array(k).fill(0), tmp;
  var len1 = nums1.length, len2 = nums2.length;
  //extract i elements from nums1 and extract k-i elements form nums2,then merge and compare
  for (var i = Math.max(0, k - len2); i <= Math.min(len1, k); i++) {
    tmp = mergeArray(getMax(nums1, i), getMax(nums2, k - i));
    if (isGreater(tmp, res, 0, 0)) res = tmp;
  }

  return res;
};

//compre the two arrays from index i and j
var isGreater = function (nums1, nums2, i, j) {
  while (i >= 0 && i < nums1.length && j >= 0 && j < nums2.length && nums1[i] == nums2[j]) {
    i++;
    j++;
  }
  return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
};

//put the max in front of the merged array
var mergeArray = function (nums1, nums2) {
  var merge = [];
  var i = 0, j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (isGreater(nums1, nums2, i, j)) {
      merge.push(nums1[i++]);
    } else {
      merge.push(nums2[j++]);
    }
  }
  for (; i < nums1.length; i++) merge.push(nums1[i]);
  for (; j < nums2.length; j++) merge.push(nums2[j]);
  return merge;
};

//get k max number preserving the order of the merged array
var getMax = function (num, k) {
  var len = num.length;
  var i = 0, j = 0, maxArray = new Array(k);
  while (i < num.length) {
    while (j > 0 && len - i + j > k && num[i] > maxArray[j - 1]) {
      j--;
    }
    if (j < k) maxArray[j++] = num[i];
    i++;
  }
  return maxArray;
};

484.Find Permutation
输入字符串表示的操作（’I’表示上升，’D’表示下降），给出最小的能得到的数。

分析：先生成对应长度的增序数字[1,2,…,n]，然后在对应连续’D’出现的范围进行反转。

var findSmallestPermutation = function (permutations) {
  var len = permutations.length;
  var res = new Array(len + 1).fill(0);
  res.forEach(function (item, index, array) {
    array[index] = index + 1;
  });
  var start = 0, end = 0;
  while (start < len) {
    while (permutations[end] == 'D') {
      end++;
    }
    if (end > start) reverse(res, start, end);
    start = end = end + 1;
  }
  return res;
};

var reverse = function (nums, start, end) {
  var tmp;
  while (start < end) {
    tmp = nums[start];
    nums[start++] = nums[end];
    nums[end--] = tmp;
  }
};