-
哈希表——算法专项刷题（五）
五、哈希表
哈希表多用于辅助记录是否存在key或者通过key找下标value
5.1插入、删除和随机访问都是O(1)的容器
设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构：
- insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。
- remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false 。
- getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。
示例 :
输入: inputs = [“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”]
[[], [1], [2], [2], [], [1], [2], []]
输出: [null, true, false, true, 2, true, false, 2]
解释:
-
RandomizedSet randomSet = new RandomizedSet(); // 初始化一个空的集合
-
randomSet.insert(1); // 向集合中插入 1 ， 返回 true 表示 1 被成功地插入
-
randomSet.remove(2); // 返回 false，表示集合中不存在 2
-
randomSet.insert(2); // 向集合中插入 2 返回 true ，集合现在包含 [1,2]
-
randomSet.getRandom(); // getRandom 应随机返回 1 或 2
-
randomSet.remove(1); // 从集合中移除 1 返回 true 。集合现在包含 [2]
-
randomSet.insert(2); // 2 已在集合中，所以返回 false
-
randomSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
提示：
-2^31 <= val <= 2^31 - 1- 最多进行
2 * 10^5 次insert，remove和getRandom方法调用 - 当调用
getRandom方法时，集合中至少有一个元素
思路： 使用list集合存储元素，使用map集合辅助存储元素和在list集合中的下标，方便删除操作
注意点： 在删除操作时，让list中最后一个元素覆盖待删除元素，注意更新元素下标和删除元素
class RandomizedSet { int size = 0; Map<Integer,Integer> map; List<Integer> list; static Random rd = new Random(); /** Initialize your data structure here. */ public RandomizedSet() { list = new ArrayList(); map = new HashMap(); } /** 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,size); 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 idx = map.get(val); //获取最后一个元素 int num = list.get(--size); //覆盖 list.set(idx,num); map.put(num,idx); map.remove(val); list.remove(size); return true; } /** Get a random element from the set. */ public int getRandom() { return list.get(rd.nextInt(size)); } }- 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
5.2有效的变位词
给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。
注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。
示例 1:
- 输入: s = “anagram”, t = “nagaram”
- 输出: true
提示:
1 <= s.length, t.length <= 5 * 104sandt仅包含小写字母
思路： 两字符串都是小写字母，使用长度为26的数组统计词频
注意点：如果两个字符串完全相同，根据题意是不符合条件的
class Solution { public boolean isAnagram(String s, String t) { if(s.equals(t) || s.length() != t.length()) return false; int[] num1 =new int[26]; for (int i = 0; i < s.length(); i++) { num1[s.charAt(i) - 'a']++; num1[t.charAt(i) - 'a']--; } for (int i = 0; i < 26; i++) { if(num1[i] != 0) return false; } 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
进阶：如果不全为小写字母
思路： 使用哈希表
class Solution { public boolean isAnagram(String s, String t) { if(s.equals(t) || s.length() != t.length()) return false; Map<Character,Integer> map = new HashMap<>(); int len = s.length(); for (int i = 0; i < len; i++) { char ch = s.charAt(i); map.put(ch,map.getOrDefault(ch,0)+1); } for (int i = 0; i < len; i++) { char ch = t.charAt(i); map.put(ch,map.getOrDefault(ch,0)-1); if(map.get(ch) < 0){ return false; } } 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
5.3外星语言是否排序
某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
示例 1：
-
输入：words = [“hello”,“leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz”
-
输出：true
-
解释：在该语言的字母表中，‘h’ 位于 ‘l’ 之前，所以单词序列是按字典序排列的。
提示：
- 1 <= words.length <= 100
- 1 <= words[i].length <= 20
- order.length == 26
- 在 words[i] 和 order 中的所有字符都是英文小写字母。
思路： 题目意思为比较字符串是按照给定字典序的从小到大排序的，使用map统计字典序
注意点： 当字符是按照字典序时，还需要保证前一个字符串长度不能大于后一个字符串长度。
class Solution { public boolean isAlienSorted(String[] words, String order) { Map<Character,Integer> map = new HashMap(); int len = order.length(); for(int i = 0; i < len;i++){ map.put(order.charAt(i),i); } int n = words.length; for(int i = 1; i < n;i++){ String s1 = words[i-1]; String s2 = words[i]; boolean flag = false; for(int j = 0; j < s1.length() && j < s2.length();j++){ char c1 = s1.charAt(j); char c2 = s2.charAt(j); if(map.get(c1) < map.get(c2)){ flag = true; break; }else if(map.get(c1) > map.get(c2)) { return false; } } // 两字符串比较的所有字符是相等的，需要比较两字符长度 if(!flag && s1.length() > s2.length()) return false; } 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
5.4变位词组
给定一个字符串数组
strs，将 变位词 组合在一起。 可以按任意顺序返回结果列表。注意： 若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。
示例 1:
-
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
-
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]仅包含小写字母
思路： 可以选择对字符串进行排序然后比较是否相同，也可以使用map集合key是字符+出现次数的拼接(防止字符相同个数不同的情况)
注意点： 拼接时注意转成char类型的字符
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String,List<String>> map = new HashMap(); for(String str : strs){ int[]count = new int[26]; int len = str.length(); for(int i = 0; i < len; i++){ count[str.charAt(i) - 'a']++; } StringBuffer sb = new StringBuffer(); for(int i = 0; i < 26;i++){ if(count[i] != 0){ sb.append((char) ('a'+i)); sb.append(count[i]); } } String key = sb.toString(); List<String>list = map.getOrDefault(key,new ArrayList<String>()); list.add(str); map.put(key,list); } return new ArrayList<>(map.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
5.5最小时间差
给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1：
-
输入：timePoints = [“23:59”,“00:00”]
-
输出：1
提示：
2 <= timePoints <= 2 * 104timePoints[i]格式为 “HH:MM”
思路： 对集合进行从小到大排序，相邻的两个时间点差值最小
注意点： 如果时间个数大于 24 * 60 就会出现至少有两个时间点相同，直接返回0，有可能首位的时间差最小，比如
"23:59","00:00"这时需要另外计算首位的时间差，用首时间 + 24 * 60 减去尾时间class Solution { public int findMinDifference(List<String> timePoints) { int size = timePoints.size(); // 有相同的时间 if(size > 24 * 60) return 0; // 排序 Collections.sort(timePoints); String preTime = timePoints.get(0); int ans = Integer.MAX_VALUE; for (int i = 1; i < size ; i++) { String curTime = timePoints.get(i); int temp = getTime(curTime) - getTime(preTime); ans = Math.min(ans,temp); preTime = curTime; } //计算首位的时间差 ans = Math.min(getTime(timePoints.get(0)) + 24 * 60 - getTime(timePoints.get(size - 1)),ans ); return ans; } public int getTime(String s){ return (s.charAt(0) * 10 + s.charAt(1)) * 60 + s.charAt(3) * 10 + s.charAt(4); } }- 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
5.6最近最少使用缓存
运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity)以正整数作为容量 capacity 初始化 LRU 缓存int get(int key)如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释:
- LRUCache lRUCache = new LRUCache(2);
- lRUCache.put(1, 1); // 缓存是 {1=1}
- lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
- lRUCache.get(1); // 返回 1
- lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
- lRUCache.get(2); // 返回 -1 (未找到)
- lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
- lRUCache.get(1); // 返回 -1 (未找到)
- lRUCache.get(3); // 返回 3
- lRUCache.get(4); // 返回 4
提示：
-
1 <= capacity <= 3000
-
0 <= key <= 10000
-
0 <= value <= 10^5
-
最多调用 2 * 10^5 次 get 和 put
思路： 双向链表+map，将最新使用的结点插入链表头结点(head)之后，最旧未使用的结点就是tail结点前的结点。map存储 key -> node 辅助查找是否存在key
注意点： 在移除结点时，需要把map中存储的key也移除
class LRUCache { class Node{ Node next,pre; int key,val; public Node(){ } public Node(int key, int val){ this.key = key; this.val = val; } } Node head = new Node(); Node tail = new Node(); int size = 0; Map<Integer,Node> map; // 删除node结点 public void delete(Node node){ node.next.pre = node.pre; node.pre.next = node.next; } //头插法 public void add(Node node){ head.next.pre = node; node.next = head.next; head.next = node; node.pre = head; } //将最新用过的结点移到头结点 public void moveHead(Node node){ delete(node); add(node); } public LRUCache(int capacity) { size = capacity; head.next = tail; tail.pre = head; map = new HashMap<>(); } public int get(int key) { if( !map.containsKey(key)) return -1; Node node = map.get(key); moveHead(node); return node.val; } public void put(int key, int value) { if(map.containsKey(key)){ Node node = map.get(key); node.val = value; map.put(key,node); moveHead(node); }else{ if(map.size() == size){ Node node = tail.pre; delete(node); map.remove(node.key); } Node node = new Node(key,value); map.put(key,node); add(node); } } }- 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
- 90
- 91
- 92
- 93
- 94
-
相关阅读:
华为云王楠楠：分布式云原生全域调度的技术和实践
损失函数（Loss Function）与代价函数（Cost Function）、目标函数（Objective Function）区别
答对这3个面试问题，薪资直涨20K
网络接口登录方法获取cookie
【bugfix】解决Redis缓存键清理问题
Nature文章|博士后对就业更有信心 但仍是学术界的苦力
【03】Charles_ mock服务端返回数据Maplocal
Vue3+Typescript+Vite实现网易云音乐年活动主导色
防火墙防火墙
【Harmony OS】【ArkUI】ets开发 图形与动画绘制
- 原文地址：https://blog.csdn.net/qq_52595134/article/details/127961971
