哈希表

哈希表是一种常见的数据结构，在解决算法面试题的时候常常须要用到哈希表。哈希表最大的长处是高效，在哈希表中插入、删除或查找一个元素都只须要 O（1）的工夫。因而，哈希表常常被用来优化工夫效率。

哈希表的设计

设计哈希表的前提是待存入的元素须要一个能计算本人哈希值的函数。

哈希表最重要的特点是高效，只须要 O(1)的工夫就能将元素存入或读出。

30. 插入、删除和随机拜访都是 O(1)的容器

设计一个数据结构，使如下 3 个操作的工夫复杂度都是 O（1）。

字段转数组不就是 O(N)?

/**
 * Initialize your data structure here.
 */
var RandomizedSet = function () {this.numToLocation = new Map();
    this.nums = []};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {if (this.numToLocation.has(val)) {return false}
    this.numToLocation.set(val, this.nums.length);
    this.nums.push(val);
    return true;
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {if (!this.numToLocation.has(val)) {return false;}
    let location = this.numToLocation.get(val);
    this.numToLocation.set(this.nums[this.nums.length - 1], location);
    this.numToLocation.delete(val);
    // 数组删除对应，这里是把数据最末位的元素笼罩要删除的元素，再把数组长度减 1，通过这种技巧来达到工夫复杂度为 O(1)
    this.nums[location] = this.nums[this.nums.length - 1];
    this.nums.length--;
    return true;
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
    // 随机生成 0 到 this.nums.length 范畴内的一个整数
    let p = parseInt(Math.random() * this.nums.length);
    return this.nums[p];
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

31. 最近起码应用缓存

请设计实现一个最近起码应用（Least Recently Used，LRU）缓存，要求如下两个操作的工夫复杂度都是 O（1）

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {this.cache = new Map()
    this.capacity = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {const { cache} = this
    if(!cache.has(key)){return -1}
    const val = cache.get(key)
    cache.delete(key)
    cache.set(key, val)
    return val
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {const { cache, capacity} = this
    if(cache.has(key)){cache.delete(key)
    }
    if(cache.size === capacity){const it = cache.keys()
        cache.delete(it.next().value)
    }
    cache.set(key,value)
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

哈希表的利用

在算法面试中哈希表是常常被应用的数据结构，如用哈希表来记录字符串中每个字符呈现的次数或每个字符呈现的地位。

• 32. 无效的变位词

给定两个字符串 s 和 t，请判断它们是不是一组变位词。在一组变位词中，它们中的字符及每个字符呈现的次数都雷同，但字符的程序不能雷同。例如，”anagram” 和 ”nagaram” 就是一组变位词。

只思考英文字母，则用数组模仿哈希表

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (str1, str2) {if (str1.length !== str2.length) return false;
    if(str1 === str2) return false
    
    let counts = new Array(26).fill(0)
    for (let ch of str1) {counts[ch.charCodeAt() - 97]++
    }

    for (let ch of str2) {if (counts[ch.charCodeAt() - 97] == 0) return false
        counts[ch.charCodeAt() - 97]--
    }
    return true
};

如果思考非英文字母，则用真正的哈希表 HashMap

var isAnagram = function(str1, str2) {if(str1.length !== str2.length) return false;
  const map = new Map()

  for(let ch of str1) {map.set(ch, (map.get(ch) || 0) + 1)
  }

  for(let ch of str2) {if(!map.get(str2)) return false;
    map.set(ch, (map.get(ch) || 0) - 1)
  }

  return true
}

• 33. 变位词组

题目：给定一组单词，请将它们依照变位词分组。例如，输出一组单词 [“eat”，”tea”，”tan”，”ate”，”nat”，”bat”]，这组单词能够分成 3 组，别离是[“eat”，”tea”，”ate”]、[“tan”，”nat”] 和[“bat”]。假如单词中只蕴含英文小写字母。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {var map = new Map();
    strs.forEach((str) => {const key = str.split('').sort().join('')
        const val = (map.get(key) || [])
        val.push(str)
        map.set(key, val)
    })
    const result = [];
    for (let value of map.values()) {result.push(value);
    }

    return result
};

• 34. 外星语言是否排序

题目：有一门外星语言，它的字母表刚好蕴含所有的英文小写字母，只是字母表的程序不同。给定一组单词和字母表程序，请判断这些单词是否依照字母表的程序排序。例如，输出一组单词[“offer”，”is”，”coming”]，以及字母表程序 ”zyxwvutsrqponmlkjihgfedcba”，因为字母 ’o’ 在字母表中位于 ’i’ 的后面，因而单词 ”offer” 排在 ”is” 的后面；同样，因为字母 ’i’ 在字母表中位于 ’c’ 的后面，因而单词 ”is” 排在 ”coming” 的后面。因而，这一组单词是依照字母表程序排序的，应该输入 true。

我想到的是过滤，而后比拟，但感觉不对，没有思考了反复

var isAlienSorted = function(words, order) {const dict = {}
    for(let i = 0; i < order.length; i++) dict[order[i]] = i
    words = words.map((word) => {return word.split('').reduce((res, w) => {return res + String.fromCharCode(97 + dict[w])
        }, '')
    })
    for(let i = 1; i < words.length; i++){if(words[i] < words[i - 1]) return false
    }
    return true
};

• 35. 最小时间差

题目：给定一组范畴在 00：00 至 23：59 的工夫，求任意两个工夫之间的最小时间差。例如，输出工夫数组[“23：50″，”23：59″，”00：00”]，”23：59″ 和 ”00：00″ 之间只有 1 分钟的距离，是最小的时间差。

/**
 * @param {string[]} timePoints
 * @return {number}
 */
var findMinDifference = function(timePoints) {if (timePoints.length > 1440 || new Set(timePoints).size < timePoints.length) return 0;
    if (timePoints.length > 720) return 1;

    const times = timePoints.map(p => p.split(':').reduce((a, c, i) => a + (+c) * (i ? 1 : 60), 0));
    times.sort((a, b) => a - b).push(1440 + times[0]);

    return times.reduce((a, c, i) => i ? Math.min(a, c - times[i - 1]) : a, 1440);
};

总结

在解决算法面试题时，哈希表是常常被应用的工具，用来记录字符串中字母呈现的次数、字符串中字符呈现的地位等信息。

如果哈希表的键的数目是固定的，并且数目不太大，那么也能够用数组来模仿哈希表，数组的下标对应哈希表的键，而数组的值与哈希表的值对应。