算法-哈希表算法总结

1 哈希表模拟

思路：通过设计哈希表，模拟O(1)时间复杂度的哈希表。

// 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器
// 设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构：insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false 。getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。
class RandomizedSet {
    private Map<Integer,Integer> map;
    private List<Integer> list;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val,list.size());
        list.add(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int location = map.get(val);
        map.put(list.get(list.size() - 1),location);
        map.remove(val);
        list.set(location,list.get(list.size() - 1));
        list.remove(list.size() - 1);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random random = new Random();
        int location = random.nextInt(list.size());
        return list.get(location);
    }
}

// 剑指 Offer II 031. 最近最少使用缓存
// 运用所掌握的数据结构，设计和实现一个  LRU (Least Recently Used，最近最少使用) 缓存机制 。实现 LRUCache 类：LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
class LRUCache {

    private Map<Integer,ListNode> map;
    private ListNode head;
    private ListNode tail;
    private int capacity;

    private static class ListNode {
        int key;
        int value;
        ListNode prev;
        ListNode next;

        public ListNode (int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    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) return -1;
        moveToTail(node,node.value);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            moveToTail(map.get(key),value);
        } else {
            if (map.size() == capacity) {
                ListNode toBeDeleted = head.next;
                deleteNode(toBeDeleted);
                map.remove(toBeDeleted.key);
            }
            ListNode node = new ListNode(key,value);
            insertToTail(node);
            map.put(key,node);
        }
    }

    private void moveToTail(ListNode node,int value) {
        deleteNode(node);
        node.value = value;
        insertToTail(node);
    }

    private void deleteNode(ListNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    private void insertToTail(ListNode node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }
}

2 数组作为哈希表

思路：数组就是简单的哈希表，数组的大小是受限的。

// 242. 有效的字母异位词
// 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] hash = new int[26];
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a']++;
            hash[t.charAt(i) - 'a']--;
        }
        return allZero(hash);
    }

    private boolean allZero(int[] hash) {
        for (int item : hash) {
            if (item != 0) return false; 
        }
        return true;
    }
}

// 1002. 查找共用字符
// 给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。
class Solution {
    public List<String> commonChars(String[] words) {
        List<String> res = new ArrayList<>();
        int[] hash = new int[26];
        for (int i = 0; i < words[0].length(); i++) {
            hash[words[0].charAt(i) - 'a']++;
        }
        for (int i = 1; i < words.length; i++) {
            int[] tmpHash = new int[26];
            for (int j = 0; j < words[i].length(); j++) {
                tmpHash[words[i].charAt(j) - 'a']++;
            }
            for (int j = 0; j < 26; j++) {
                hash[j] = Math.min(hash[j],tmpHash[j]);
            }
        }
        for (int i = 0; i < 26; i++) {
            while (hash[i] > 0) {
                res.add(String.valueOf((char)(i + 'a')));
                hash[i]--;
            }
        }
        return res;
    }
}

// 剑指 Offer II 032. 有效的变位词
// 给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) return false;
        int[] hash = new int[26];
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a']++;
            hash[t.charAt(i) - 'a']--;
        }
        return allZero(hash);
    }

    private boolean allZero(int[] hash) {
        for (int item : hash) {
            if (item != 0) {
                return false;
            }
        }
        return true;
    }
}

// 剑指 Offer II 034. 外星语言是否排序
// 某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] hash = new int[order.length()];
        for (int i = 0; i < order.length(); i++) {
            hash[order.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < words.length - 1; i++) {
            if (!isSorted(words[i],words[i + 1],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++) {
            char ch1 = str1.charAt(i);
            char ch2 = str2.charAt(i);
            if (hash[ch1 - 'a'] < hash[ch2 - 'a']) {
                return true;
            } else if (hash[ch1 - 'a'] > hash[ch2 - 'a']) {
                return false;
            }
        }
        return i == str1.length();
    }
}

// 剑指 Offer II 035. 最小时间差
// 给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
class Solution {
    public int findMinDifference(List<String> timePoints) {
        if (timePoints.size() > 1440) return 0;
        boolean[] hash = new boolean[1440];
        for (int i = 0; i < timePoints.size(); i++) {
            String[] timePoint = timePoints.get(i).split(":");
            int min = Integer.parseInt(timePoint[0]) * 60 + Integer.parseInt(timePoint[1]);
            if (hash[min]) return 0;
            hash[min] = true;
        }
        return helper(hash);
    }

    private int helper(boolean[] hash) {
        int minDiff = hash.length - 1;
        int prev = Integer.MIN_VALUE;
        int first = Integer.MAX_VALUE;
        int last = Integer.MIN_VALUE;
        for (int i = 0; i < hash.length; i++) {
            if (hash[i]) {
                if (prev != Integer.MIN_VALUE) {
                    minDiff = Math.min(minDiff,i - prev);
                }   
                prev = i;
                first = Math.min(first,i);
                last = Math.max(last,i);
            }
        }
        minDiff = Math.min(minDiff,first + hash.length - last);
        return minDiff;
    }
}

3 Set作为哈希表

思路：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序。使用数组来做哈希的题目，是因为题目都限制了数值的大小。而若没有限制数值的大小，就无法使用数组来做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

// 349. 两个数组的交集
// 给定两个数组，编写一个函数来计算它们的交集。
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> tmpSet = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        for (int num : nums1) {
            tmpSet.add(num);
        }
        for (int num : nums2) {
            if (tmpSet.contains(num)) {
                resSet.add(num);
            }
        }
        int[] res = new int[resSet.size()];
        int index = 0;
        for (int num : resSet) {
            res[index++] = num;
        }
        return res;
    }
}

// 202. 快乐数
// 编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。如果 n 是快乐数就返回 true ；不是，则返回 false 。
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (n != 1 && !set.contains(n)) {
            set.add(n);
            n = getNextNum(n);
        }
        return n == 1;
    }

    private int getNextNum(int n) {
        int res = 0;
        while (n > 0) {
            int tmp = n % 10;
            res += tmp * tmp;
            n /= 10;
        }
        return res;
    }
}

4 Map作为哈希表

思路：数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。set是一个集合，里面放的元素只能是一个key，而若不仅要判断y是否存在而且还要记录y的其他信息，所以set 也不能用，需要使用哈希表。

// 1. 两数之和
// 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length == 0) return res;
        Map<Integer,Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int tmp = target - nums[i];
            if (hash.containsKey(tmp)) {
                res[0] = hash.get(tmp);
                res[1] = i;
                break;
            }
            hash.put(nums[i],i);
        }
        return res;
    }
}

// 454. 四数相加 II
// 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer,Integer> hash = new HashMap<>();
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                int tmp = num1 + num2;
                hash.put(tmp,hash.getOrDefault(tmp,0) + 1);
            }
        }
        for (int num3 : nums3) {
            for (int num4 : nums4) {
                int tmp = 0 - (num3 + num4);
                if (hash.containsKey(tmp)) {
                    res += hash.get(tmp);
                }
            }
        }
        return res;
    }
}

// 剑指 Offer II 033. 变位词组
// 给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> hash = new HashMap<>();
        for (String str : strs) {
            char[] chs = str.toCharArray();
            Arrays.sort(chs);
            String sorted = new String(chs);
            hash.putIfAbsent(sorted,new LinkedList<>());
            hash.get(sorted).add(str);
        }
        return new LinkedList<>(hash.values());
    }
}