哈希表的设计

30：插入、删除和随机访问都是O（1）的容器

:::info 题目：设计一个数据结构，使如下3个操作的时间复杂度都是O（1）。
● insert（value）：如果数据集中不包含一个数值，则把它添加到数据集中。
● remove（value）：如果数据集中包含一个数值，则把它删除。
● getRandom()：随机返回数据集中的一个数值，要求数据集中每个数字被返回的概率都相同。 :::

public class RandomSet() {
    private Map<Integer, Integer> numToLoc = new HashMap<>();
    private ArrayList<Integer> nums = new ArrayList();
    public boolean insert(Integer val) {
        if (numToLoc.containsKey(val)) {
            return false;
        }
        nums.add(val);
        numToLoc.put(val, nums.size());
        return true;
    }
    public boolean remove(Integer val) {
        if (!numToLoc.containsKey(val)) {
            return false;
        }
        int location = numToLoc.get(val);
        // 将最后一个数字换到当前位置
        numToLoc.put(nums.get(nums.size() - 1), location);
        nums.set(location - 1, nums.get(nums.size() - 1));
        // 删除数组最后一个值
        nums.remove(nums.size() - 1);
        // 从map删除val
        numToLoc.remove(val);
        return true;
    }
    @Override
    public String toString() {
        return "RandomSet{" +
                "nums=" + nums +
                '}';
    }
    public Integer getRandomVal() {
        Random random = new Random();
        int randomLoc = random.nextInt(nums.size());
        return nums.get(randomLoc);
    }
}

31：最近最少使用缓存

:::info 题目：请设计实现一个最近最少使用（Least Recently Used，LRU）缓存，要求如下两个操作的时间复杂度都是O（1）。
● get（key）：如果缓存中存在键key，则返回它对应的值；否则返回-1。
● put（key，value）：如果缓存中之前包含键key，则它的值设为value；否则添加键key及对应的值value。在添加一个键时，如果缓存容量已经满了，则在添加新键之前删除最近最少使用的键（缓存中最长时间没有被使用过的元素）。 :::

public LRUCache {
    private Map<Integer, Node> map = new HashMap<>();
    int capacity;
    Node head;
    Node tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 初始化哨兵头尾节点
        // 有了哨兵节点，在增删真实节点时，就可以不用考虑头尾的特殊处理
        Node dummyHead = new Node(0, 0);
        Node dummyTail = new Node(0, 0);
        head = dummyHead;
        tail = dummyTail;
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        if (map.containsKey(key)) {
            moveToTail(map.get(key), map.get(key).val);
            return map.get(key).val;
        }
        return -1;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.get(key).val = value;
            moveToTail(map.get(key), value);
        }
        Node node = new Node(key, value);
        if (map.size() < capacity) {
            insertTail(node);
        } else {
            map.remove(head.next.key);
            deleteNode(head.next);
            insertTail(node);
        }
        map.put(key, node);
    }
    private void deleteNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void insertTail(Node node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }
    private void moveToTail(Node node, int newVal) {
        // 更新node值
        node.val = newVal;
        // 先从链表中删除node
        this.deleteNode(node);
        // insert
        this.insertTail(node);
    }
    private class Node {
        public Node prev;
        public Node next;
        public int key;
        public int val;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        Node p = head.next;
        while (p != tail) {
            stringBuilder.append("{").append(p.key).append(",").append(p.val).append("}");
            if (p.next != tail) {
                stringBuilder.append(" -> ");
            }
            p = p.next;
        }
        return stringBuilder.toString();
    }
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        System.out.println(lruCache);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache);
        lruCache.put(8, 8);
        lruCache.put(9, 9);
        lruCache.get(8);
        System.out.println(lruCache);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(4, 4);
        lruCache.put(5, 5);
        System.out.println(lruCache);
        lruCache.get(1);
        System.out.println(lruCache);
        lruCache.put(6, 6);
        System.out.println(lruCache);
    }
}

哈希表的应用

32：有效的变位词

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

public class Anagram {
    public boolean isAnagram(String s1, String s2) {
        if(s1.lenth() != s2 || s1.equals(s2)) {
            false;
        }
        Map<Character, Integer> map = HashMap<>();
        for(char c : s1.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for(char c : s2.toCharArray()) {
            if(!map.containsKey(c) || map.get(c) == 0) {
                return false;
            }
            map.put(c, map.get(c) - 1);
        }
        return true;
    }
}

33：变位词组

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

public GroupAnagram {
    public static List<List<String>> groupAnagram(List<String> strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String sortedStr = new String(arr);
            if (groups.containsKey(sortedStr)) {
                groups.get(sortedStr).add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                groups.put(sortedStr, list);
            }
        }
        return new ArrayList<>(groups.values());
    }
    public static void main(String[] args) {
        List<String> strs = Arrays.asList("eat","tea","tan","ate","nat","bat");
        System.out.println(groupAnagram(strs));
    }
}

34：外星语言是否排序

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

public class isAlienSorted {
    public static boolean isAlienSorted(List<String> strs, String order) {
        int[] orderArr = new int[26];
        for (int i = 0; i < order.length(); i++) {
            // i 就是当前字母的顺序
            orderArr[order.charAt(i) - 'a'] = i;
        }
        for (int i = 1; i < strs.size(); i++) {
            boolean isSorted = isWordSorted(strs.get(i - 1), strs.get(i), orderArr);
            if (!isSorted) {
                return false;
            }
        }
        return true;
    }
    private static boolean isWordSorted(String word1, String word2, int[] orderArr) {
        for (int i = 0; i < word1.length() && i < word2.length(); i++) {
            char ch1 = word1.charAt(i);
            char ch2 = word2.charAt(i);
            if (orderArr[ch1 - 'a'] < orderArr[ch2 - 'a']) {
                return true;
            }
            if (orderArr[ch1 - 'a'] > orderArr[ch2 - 'a']) {
                return false;
            }
        }
        // 如果前序字母都相同，则短的单词排前面
        return word1.length() <= word2.length();
    }
    public static void main(String[] args) {
        List<String> strs = Arrays.asList("offer", "is", "coming");
        System.out.println(isAlienSorted(strs, "zyxwvutsrqponmlkjihgfedcba"));
    }
}

35：最小时间差

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

public class MinDifference {
    public static int findMinDifference(String[] strs) {
        // 将时间转换成从秒数，然后计入hash表
        boolean[] timeTable = new boolean[1440];
        for(String str : strs) {
            String[] arr = str.spilit(":")
            int count = Integer.parse(arr[0]) * 60 + Integer.parse(arr[1]);
            if(timeTable[count]) {
                // 出现相同的两个时间，那最小时间差就是0;
                return 0;
            }
            timeTable[count] = true;
        }
        // 遍历 timeTable 计算最小时间差
        int prev = -1;
        int first = Integer.MAX_VALUE;
        int last = -1;
        int minDiff = Integer.MAX_VALUE;
        for(int i = 0; i < timeTable.size(); i++) {
            if(timeTable[i]) {
                if(prev >= 0 ) {
                    minDiff = Math.min(minDiff, i - prev);
                }
                prev = i;
                first = Math.min(first, i);
                last = Math.max(last, i;)
            } 
        }
        return Math.min(1440-last+first, minDiff);
    }
}

我是一个程序猿

chapter5 哈希表