算法：（五）哈希表

哈希表相关知识： 从Java源码探索哈希表的前世今生

5.1 哈希表的设计

面试题30：插入、删除和随机访问都是O(1)的容器

题目：设计一个数据结构，使如下三个操作的时间复杂度都是O(1)。

• insert(val)：如果数据集中不包含一个值，则把它添加到数据集中。
• remove(val)：如果数据集中包含一个值，则把它删除。
• getRandom()：随机返回数据集中的一个数值，要求数据集中每个数字被返回的概率都相同。

HashMap<Integer, Integer> numToLocation = new HashMap<>(16);
ArrayList<Integer> nums = new ArrayList();

public boolean insert(int val){
    if(numToLocation.containsKey(val)){
        return false;
    }
    numToLocation.put(val, nums.size());
    nums.add(val);
    return true;
}

public boolean remove(int val){
    /**
     * ArrayList的remove操作的时间复杂度是O(n)，要如何保证本方法的时间复杂度是O(1)？
     * 通过只删除最后一个元素，然后将原本的最后一个元素放置到待删除元素的位置
     * 将O(n)的删除操作化为O(1)的删除最后一个元素的操作
     */
    if(!numToLocation.containsKey(val)){
        return false;
    }
    // 通过HashMap获取要删除元素的下标
    int location = numToLocation.get(val);
    // 更新HashMap，location位置为ArrayList的最后一个元素
    numToLocation.put(nums.get(nums.size() - 1), location);
    // 删除HashMap中要删除元素的键值对
    numToLocation.remove(val);
    // 设置ArrayList的location位置为ArrayList的最后一个元素
    nums.set(location, nums.get(nums.size() - 1));
    // 只删除ArrayList的最后一个元素
    nums.remove(nums.size() - 1);
    return true;
}

public int getRandom(){
    Random random = new Random();
    // random.nextInt(int n)：返回一个[0,n)，即 0 ~ n-1 的随机int数
    int r = random.nextInt(nums.size());
    return nums.get(r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

面试题31：最近最少使用缓存（重点）

题目：请设计实现一个最近最少使用（Least Recently Used， LRU）缓存，要求如下两个操作的时间复杂度都是O(1)。

• get(key)：如果缓存中存在键key，则返回它对应的值；否则返回-1
• put(key, value)：如果缓存中之前包含key，则它的值设为value；否则添加键key及对应的值value。在添加一个键时，如果缓存容量已经满了，则在添加新键之前删除最近最少使用的键（缓存中最长时间没有被使用过的元素）。

public class LRUCache {
    /**
     * 使用HasmMap和双向链表来实现LRUCache，HashMap中存放的key为要存入的key，value是双向链表的Node
     * 每次get或者put元素的时候，该元素是最新被使用的，把放到链表的尾部，则链表的头部就是最近最少被使用的元素
     * get方法要实现的功能是
     * 1. 将读取的元素节点放到链表尾部
     * 2. 返回读取的值
     * put方法要实现的功能是
     * 1. 若元素节点已存在，则把它移动到链表尾部
     * 2. 若元素节点不存在，先判断链表的长度是否达到上限，若达到上限则删除表头（HashMap中对应的元素也要删除），最后在链表的尾部添加此元素
     */
    private ListNode head;
    private ListNode tail;
    private Map<Integer, ListNode> map;
    private int capacity;

    public LRUCache(int capacity){
        map = new HashMap<>();

        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
    }

    public int get(int key){
        ListNode node = map.get(key);
        if(node != null){
            moveToTail(node, node.value);
            return node.value;
        }
        return -1;
    }

    private void put(int key, int value){
        if(map.containsKey(key)){
            moveToTail(map.get(key), value);
        } else {
            if(map.size() == capacity){
                ListNode toBeDelete = head.next;
                deleteNode(toBeDelete);
                map.remove(toBeDelete.key);
            }
            ListNode newNode = new ListNode(key, value);
            insertToTail(newNode);
            map.put(key, newNode);
        }
    }

    /**
     * 将node移动到链表末尾，在put过程中要更新node的值
     * 分两步：1. 从节点当前位置删除； 2. 在尾部插入该节点
     */
    private void moveToTail(ListNode node, int newValue) {
        deleteNode(node);
        node.value = newValue;
        insertToTail(node);
    }

    /**
     * 从链表中删除当前节点
     */
    private void deleteNode(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 将node插入到链表尾部
     */
    private void insertToTail(ListNode node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    private class ListNode{
        public int key;
        public int value;
        ListNode next;
        ListNode prev;
        public ListNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

5.2 哈希表的应用

面试题32：有效的变位词

题目：给定两个字符串s和t，请判断它们是不是一对变位词。在一组变位词中，他们中的字符及每个字符出现的次数都相同，但字符的顺序不能相同。例如，"anagram"和"nagaram"就是一组变位词。

思路：变位词一般使用hash表来进行判断；若只是英文字母，则可以考虑使用长度为26的数组来模拟hash表；若字符不限制只是英文，则要使用真正的HashMap。

public boolean isAnagram(String str1, String str2){
    if(str1.equals(str2) || str1.length() != str2.length()){
        return false;
    }
    int[] hash = new int[26];
    for (char c : str1.toCharArray()) {
        hash[c - 'a']++;
    }
    for (char c : str2.toCharArray()){
        if(hash[c - 'a'] == 0){
            return false;
        }
        hash[c - 'a']--;
    }
    return true;
}

public boolean isAnagramPro(String str1, String str2){
    if(str1.equals(str2) || str1.length() != str2.length()){
        return false;
    }
    HashMap<Character, Integer> hash = new HashMap<>();
    for (char c : str1.toCharArray()) {
        hash.put(c, hash.getOrDefault(c, 0) + 1);
    }
    for (char c : str2.toCharArray()){
        if(hash.getOrDefault(c, 0) == 0){
            return false;
        }
        hash.put(c, hash.get(c) - 1);
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

面试题33：变位词组

题目：给定一组单词，请将它们按照变位词分组。例如，输入一组单词[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]，这组单词可以分为三组，跟别是[“eat”, “tea”, “ate”]，[“tan”, “nat”]和[“bat”]。假设单词中只包含英文小写字母。

思路：分组-映射，将每个字母映射到一个质数，然后每个单词映射到每个字母对应的质数的乘积；然后使用hashmap，键为乘积，值为字符串链表

public List<List<String>> groupAnagram(String[] strs){
    /**
 	 * 26个质数数组
	 */
    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 87, 97, 101};
    HashMap<Integer, LinkedList<String>> wordHash = new HashMap<>();
    for (String str : strs) {
        int wordHashNum = 1;
        for (int i = 0; i < str.length(); i++){
            wordHashNum *= primes[str.charAt(i) - 'a'];
        }
        // 将当前str添加到wordHash对应wordHashNum的链表上
        wordHash.putIfAbsent(wordHashNum, new LinkedList<>());
        wordHash.get(wordHashNum).add(str);
    }
    return new LinkedList<>(wordHash.values());
}

public List<List<String>> groupAnagramPro(String[] strs){
    /**
     * 同样是映射的思想，将变位词直接通过字母的排序映射为同一个单词，用这个单词代替质数
     * 这个方法更直观
     */
    HashMap<String, LinkedList<String>> wordHash = new HashMap<>();
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String sortedStr = chars.toString();
        // 将当前str添加到wordHash对应sortedStr的链表上
        wordHash.putIfAbsent(sortedStr, new LinkedList<>());
        wordHash.get(sortedStr).add(str);
    }
    return new LinkedList<>(wordHash.values());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

面试题34：外星语言是否排序

题目：有一门外星语言，它的字母表刚好是所有的英文小写字母的合集，但是字母表的顺序不同。给定一组单子和字母表顺序，请判断这些单词是否按照字母表的顺序进行排序。例如，输入一组单词[“offer”, “is”, “coming”]，以及字母表顺序"zyxwvutesrqponmlkjihgfedcba"，由于字母’o’在字母表中的位置位于’i’前面，因此"offer"排在"is"的前面；同样，由于字母’i’在字母表中的顺序位于’c’的前面，因此单词"is"排在"coming"的前面。因此这一组单词是按照字母表顺序排序的，应该输出true。

public boolean isAlienSorted(String[] strs, String order){
    // 使用数组模拟hash表，存放字母表的顺序
    int[] hash = new int[26];
    for (int i = 0; i < order.length(); ++i) {
        hash[order.charAt(i) - 'a'] = i;
    }
    // 每个单词逐一比对
    for (int i = 1; i < strs.length; ++i){
        if(!isSorted(strs[i - 1], strs[i], hash)){
            return false;
        }
    }
    return true;
}

private boolean isSorted(String str1, String str2, int[] hash) {
    int i = 0;
    for(; i < str1.length() && i < str2.length(); i++){
        // 相同位置的字符比较，如果不同，则必有前后顺序；如果相同，则比较下一个字符
        if(hash[str1.charAt(i) - 'a'] < hash[str2.charAt(i) - 'a']){
            return true;
        }
        if(hash[str1.charAt(i) - 'a'] > hash[str2.charAt(i) - 'a']){
            return false;
        }
    }
    return i == str1.length();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

面试题35：最小时间差

题目：给定一组范围在00:00至23:59的时间，求任意两个时间之间的最小时间差。例如，输入时间数组[“23:50”, “23:59”, “00:00”]， "23:59"与"00:00"之间之有一分钟的间隔，是最小的时间差。

public int findMinDifference(String[] times){
    /**
     * 用数组模拟hash表来记录出现的时间，然后在数组中求两个时间之间的最小距离
     */
    if(times.length > 1440){
        return 0;
    }
    boolean[] minutes = new boolean[1440];
    for(String str : times){
        String[] split = str.split(":");
        int hour = Integer.parseInt(split[0]);
        int minute = Integer.parseInt(split[1]);
        int time = hour * 60 + minute;
        if(minutes[time] == true){
            return 0;
        }
        minutes[time] = true;
    }
    return findMin(minutes);
}

private int findMin(boolean[] minutes) {
    int minDiff = minutes.length - 1;
    // 前一个为true的下标
    int prev = -1;
    // 第一个为true的下标
    int first = minutes.length - 1;
    // 最后一个为true的下标
    int last = -1;
    for (int i = 0; i < minutes.length; i++) {
        if(minutes[i]){
            if(prev >= 0){
                minDiff = Math.min(i - prev, minDiff);
            }
            prev = i;
            first = Math.min(i, first);
            last = Math.max(i, last);
        }
    }
    // 判断一天最后一个时间和第二天第一个时间的时间差，与前一天之内的最小时间差的大小，取较小的值
    minDiff = Math.min(minDiff, minutes.length - last + first);
    return minDiff;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43