经典算法之哈希算法和贪心算法

哈希算法

哈希（Hash）也称为散列，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，这个输出值就是散列值。

提到了哈希，那肯定就要说下哈希表，那么什么是哈希表呢？

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

当然，哈希算法也可以用在很多场景，比如加密中，因为哈希算法通常是单向的。

我们先来看一个很简单也是很多人入门的算法题：

两数之和

题目如下：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出
和为目标值 target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。
但是，数组中同一个元素在答案里不能重复出现。

示例 ：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

这道题有两道解法，一般我们会想到最简单的暴力解法：

var twoSum = function(nums, target) {
  for (var i = 0; i < nums.length; i++) {
    for (var j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
};

但是你会发现这个解法的时间复杂度是 O(n²),所以我们可以引入哈希来优化：

var twoSum = function(nums, target) {
  var map = new Map(); // 利用ES6的Map
  for (var i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      // 查看map是否存在
      return [map.get(target - nums[i]), i];
    }
    map.set(nums[i], i); // 加入Map
  }
};

这样我们就把时间复杂度优化到了 O(n)。

罗马数字转整数

题目如下：

这也是一条很经典的哈希算法题，而且还可以衍生出很多问题，下一道题就是从这题衍生出来的：

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

> 字符          数值
> I             1
> V             5
> X             10
> L             50
> C             100
> D             500
> M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，
例如4不写做IIII，而是IV。数字1在数字5的左边，所表示的数等于大数5减小数1得到的数值4。
同样地，数字9表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III"
输出: 3

算法代码如下：

var romanToInt = function(s) {
  const map = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
    IV: 4,
    IX: 9,
    XL: 40,
    XC: 90,
    CD: 400,
    CM: 900,
  };

  let sum = 0;
  let i = 0;
  while (i < s.length) {
    if (map[s.substring(i, i + 2)]) {
      // 获取字符串的两个字段，如果map中存在就相加数
      sum += map[s.substring(i, i + 2)];
      i = i + 2;
    } else {
      // 不存在就在map找对应的一个字段
      sum += map[s.substring(i, i + 1)];
      i++;
    }
  }
  return sum;
};

贪心算法

什么是贪心算法呢？

贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），从而达到全局的最优（全局最优解）。

首先我们接着上一题哈希算法的罗马数字转整数的衍生题：

整数转罗马数

这一题在 LeetCode 给出了中等：

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

> 字符          数值
> I             1
> V             5
> X             10
> L             50
> C             100
> D             500
> M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。

示例:

输入: num = 3
输出: "III"

算法代码：

var intToRoman = function(num) {
  // 这里需要注意顺序，应该从大到小，不然是错的
  var hash_map = {
    M: 1000,
    CM: 900,
    D: 500,
    CD: 400,
    C: 100,
    XC: 90,
    L: 50,
    XL: 40,
    X: 10,
    IX: 9,
    V: 5,
    IV: 4,
    I: 1,
  }; // 初始化哈希
  var str = "";
  // 贪心算法
  for (const i in hash_map) {
    while (num >= hash_map[i]) {
      // 如果总数比遍历的数字大，把传进来的数字减遍历的数字
      str += i; // 字符串加上
      num -= hash_map[i]; // 总数减去遍历的数字
    }
  }
  return str;
};

这道题其实可以看出贪心算法的核心就是找到一个最大的值，不断的相减，然后最后一直遍历，这道题虽然是中等，但稍微思考下还是可以得出来的。

分数背包问题

背包问题是很经典的算法题了，最经典的就是动态规划的背包问题，我们在前面讲过，链接 (opens new window)在这里。但是动态规划的版本是只能装入整数的物品，贪心算法的版本可以装入分数的物品。 我们还是先来看下变量：

const values = [3, 4, 5], // 每个物品的价值
  weights = [2, 3, 4], // 每个物品的重量
  capacity = 5, // 限制的重量
  n = values.length;

问题和变量跟动态规划版本的不变，但是算法肯定不一样：

function knapSack(capacity, weights, values) {
  const n = values.length;
  let load = 0;
  let val = 0;
  for (let i = 0; i < n && load < capacity; i++) {
    // 重量数不能超过总数
    if (weights[i] <= capacity - load) {
      // 如果物品重量小于总数减去已经放进去的物品重量
      val += values[i];
      load += weights[i];
    } else {
      // 整数不能放进去就计算能够装入部分的比例
      const r = (capacity - load) / weights[i];
      val += r * values[i];
      load += r * weights[i];
    }
  }
  return val;
}

总结

无论是哈希算法还是贪心算法，它们经常伴随其他算法一起出现，其概念不是算很难的，比动态规划或者其它算范都要好理解，多接触相关算法就可以了。