大厂算法面试 7 天冲刺：第4天- 哈希表与堆算法深度解析 - 高频面试题与 Java 实战

第4天：哈希表与堆算法深度解析 - 高频面试题与 Java 实战

1. 哈希表与堆的核心概念

1.1 哈希表（Hash Table）

哈希表是一种基于哈希函数实现的键值对存储数据结构，其核心特点是：

• O(1) 平均时间复杂度的插入、删除和查询操作。
• 依赖哈希函数将键映射到数组索引，可能会发生哈希冲突，常见解决方案有链地址法和开放寻址法。
• 在 Java 中，最常用的哈希表实现是 HashMap、HashSet。

1.2 堆（Heap）

堆是一种特殊的二叉树数据结构，满足堆属性：

• 最大堆（Max Heap）：任意节点的值 ≥ 其子节点的值（根节点最大）。
• 最小堆（Min Heap）：任意节点的值 ≤ 其子节点的值（根节点最小）。
• 堆常用于优先级队列（Priority Queue），在 Java 中可以使用 PriorityQueue 实现。

2. 高频算法题及解决方案

问题1：前 K 个高频元素（Top K Frequent Elements）

问题描述

给定一个整数数组 nums，找出其中出现频率最高的 K 个元素。

示例

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

解法：最小堆（O(n log k)）

• 使用 HashMap 统计频率
• 使用 PriorityQueue（最小堆）维护前 K 个高频元素

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int num : nums) {
        countMap.put(num, countMap.getOrDefault(num, 0) + 1);
    }
    
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(countMap::get));
    
    for (int num : countMap.keySet()) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll();
    }
    return result;
}

问题2：LRU 缓存机制（LRU Cache）

问题描述

实现 LRU (Least Recently Used) 缓存，支持以下操作：

1. get(key): 如果 key 存在于缓存中，则返回值，否则返回 -1。
2. put(key, value): 插入 key-value，如果容量已满，则移除最久未使用的元素。

示例

LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 移除 key 2
cache.get(2); // 返回 -1 (已删除)

解法：哈希表 + 双向链表

• 哈希表（O(1) 查询） 记录 key-value 位置。
• 双向链表（维护访问顺序） 头部存最新访问数据，尾部存最久未使用数据。

class LRUCache {
    class DLinkedNode {
        int key, value;
        DLinkedNode prev, next;
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, DLinkedNode> cache;
    private final DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new DLinkedNode(-1, -1);
        this.tail = new DLinkedNode(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        DLinkedNode node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            DLinkedNode node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            if (cache.size() >= capacity) {
                removeLRUNode();
            }
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
        }
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(DLinkedNode node) {
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void removeLRUNode() {
        DLinkedNode lruNode = tail.prev;
        removeNode(lruNode);
        cache.remove(lruNode.key);
    }
}

问题3：字母异位词分组（Group Anagrams）

问题描述

给定字符串数组 strs，将字母异位词（anagrams）分组。

示例

Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

解法：哈希表 + 排序

• 对每个字符串排序，相同字母异位词的排序结果相同。
• 用哈希表存储 排序后字符串作为 key，原始字符串作为 value。

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String sortedStr = new String(chars);
        map.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);
    }
    return new ArrayList<>(map.values());
}

3. 总结（Summary）

🔥 掌握哈希表与堆的核心算法，助力大厂面试冲刺！ 🚀