算法-哈希表算法总结
2021-11-21 本文已影响0人
攻城老狮
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());
}
}
