哈希表——算法专项刷题（五）

怼烎@ 2024-03-31 09:43 96阅读 0赞

### 五、哈希表 ###

哈希表多用于辅助记录是否存在key或者通过key找下标value

#### 5.1插入、删除和随机访问都是O(1)的容器 ####

[原题链接][Link 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));
        }
    }

#### 5.2有效的变位词 ####

[原题链接][Link 2]

给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。

注意：若 s 和 t 中每个字符出现的次数都相同且**字符顺序不完全相同**，则称 s 和 t 互为变位词（字母异位词）。

**示例 1:**

*  输入: s = “anagram”, t = “nagaram”
 *  输出: true

**提示:**

*  `1 <= s.length, t.length <= 5 * 104`
 *  `s` and `t` 仅包含小写字母

**思路：** 两字符串都是小写字母，使用长度为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;
              
    
        }
    }

**进阶：如果不全为小写字母**

**思路：** 使用哈希表

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;
    
        }
    }

#### 5.3外星语言是否排序 ####

[原题链接][Link 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;
        }
    }

#### 5.4变位词组 ####

[原题链接][Link 4]

给定一个字符串数组 `strs` ，将 **变位词** 组合在一起。 可以按任意顺序返回结果列表。

**注意：** 若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

示例 1:

*  输入: strs = \[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”\]
 *  输出: \[\[“bat”\],\[“nat”,“tan”\],\[“ate”,“eat”,“tea”\]\]

**提示：**

*  `1 <= strs.length <= 104`
 *  `0 <= strs[i].length <= 100`
 *  `strs[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());
    
        }
    }

#### 5.5最小时间差 ####

[原题链接][Link 5]

给定一个 24 小时制（小时:分钟 **“HH:MM”**）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

**示例 1：**

*  输入：timePoints = \[“23:59”,“00:00”\]
 *  输出：1

**提示：**

*  `2 <= timePoints <= 2 * 104`
 *  `timePoints[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);
                
    
        }
    }

#### 5.6最近最少使用缓存 ####

[原题链接][Link 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);
    
    
    
    
            }
    
        }
    
    
    }

[Link 1]: https://leetcode.cn/problems/FortPu/
[Link 2]: https://leetcode.cn/problems/dKk3P7/
[Link 3]: https://leetcode.cn/problems/lwyVBB/
[Link 4]: https://leetcode.cn/problems/sfvd7V/
[Link 5]: https://leetcode.cn/problems/569nqc/
[Link 6]: https://leetcode.cn/problems/OrIXps/