思路：通过设计哈希表，模拟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()); } }
