TL - Java高级架构师教程-剑指offer数据结构与算法（完结无密）

下课仔： 图L课堂-Java高级架构师教程-剑指Offer数据结构与算法|完结无密

在 Java 技术栈的面试晋升之路上，算法题往往是一道分水岭。特别是对于资深开发者或架构师岗位，面试官关注的不再仅仅是代码能否“AC”（通过测试用例），而是你编码背后的数据结构选型、内存模型理解以及系统设计的权衡。

很多时候，你在做副业项目（如短视频应用）或备考高级认证（如系规、HCIA）时积累的工程经验，其实可以完美映射到算法题的解题思路中。

今天我们选取《剑指 Offer》中的三道典型题目，分别对应哈希与索引设计、二叉树与存储引擎、并发与缓存架构，带你从“写出代码”进化到“设计系统”。

题目一：复杂链表的复制（考察：深拷贝与哈希映射）

《剑指 Offer》35：复杂链表的复制 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或 null。

1. 基础解法：哈希表映射

这是最直观的思路：利用 Java 的 HashMap 建立 原节点 -> 新节点 的映射关系。这利用了哈希表 $O(1)$ 的快速查找特性。

class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
    }
}
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        
        // Key: 原节点, Value: 新节点
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        
        // 第一轮遍历：创建新节点并存入 Map
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        
        // 第二轮遍历：组装 next 和 random 指针
        cur = head;
        while (cur != null) {
            // map.get(cur) 拿到新节点，map.get(cur.next) 拿到下一个新节点
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        
        return map.get(head);
    }
}

2. 架构师思维：空间换时间 vs. 原地算法

• 面试官追问：“如果链表节点达到千万级，你的 HashMap 占用多少内存？能否优化空间复杂度到 $O(1)$？”
• 架构视角解析：
  • HashMap 方案：时间 $O(n)$，空间 $O(n)$。在业务代码中，简单、可读性高往往是首选，除非面临明确的内存压力（如 Android 开发）。
  • 原地拼接法：将新节点直接拼接在原节点后面（如 1 -> 1' -> 2 -> 2'），利用原链表的指针关系完成 random 定位，最后拆分。
  • 工程启示：这对应了系统设计中的数据局部性原理。在处理海量数据（如 Kafka 消息拷贝、Netty ByteBuf 拷贝）时，尽量减少对象创建和随机内存访问，利用 CPU 缓存行提升性能。

题目二：二叉搜索树与双向链表（考察：数据结构变换）

《剑指 Offer》36：二叉搜索树与双向链表 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新节点，只能调整树中节点指针的指向。

1. 核心解法：中序遍历 + 虚拟头节点

二叉搜索树（BST）的中序遍历结果天然有序。我们在递归遍历时，记录前驱节点 prev，将其与当前节点 cur 进行双向绑定。

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node() {}
    public Node(int _val) { val = _val; }
}
class Solution {
    Node prev, head;
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        dfs(root);
        // 题目要求循环，最后首尾相连
        head.left = prev;
        prev.right = head;
        return head;
    }
    void dfs(Node cur) {
        if (cur == null) return;
        
        dfs(cur.left); // 左
        
        // 中：处理指针逻辑
        if (prev != null) {
            prev.right = cur;
        } else {
            // prev 为空，说明当前是头节点
            head = cur;
        }
        cur.left = prev;
        prev = cur;
        
        dfs(cur.right); // 右
    }
}

2. 架构师思维：树的形态演变与索引结构

• 面试官追问：“为什么数据库索引通常使用 B+ 树而不是二叉搜索树（BST）？”
• 架构视角解析：
  • 高度差异：BST 在极端情况下会退化为链表，查询复杂度 $O(n)$。而 B+ 树是一个矮胖的多路平衡查找树，能大大减少磁盘 I/O 次数。
  • 范围查询：本题将 BST 转为了链表，本质上揭示了有序数据的物理逻辑。B+ 树的所有叶子节点通过指针连接（正如本题中的双向链表），这使得 SQL 的范围查询（SELECT * FROM table WHERE id > 100）极其高效，只需遍历叶子节点链表即可，无需回溯父节点。
  • 工程启示：理解树与链表的转换，是深入理解 MySQL InnoDB 和 Elasticsearch 等存储引擎原理的基础。

题目三：LRU 缓存机制（考察：哈希 + 双向链表）

《剑指 Offer》（延伸）：LRU 缓存机制 设计 LRU (最近最少使用) 缓存结构，在 $O(1)$ 时间复杂度内完成 get 和 put 操作。 这是 Java 架构师面试中的压轴题，直接考察对缓存组件（如 Redis、Guava Cache）底层的理解。

1. 核心代码实现

利用 HashMap 查找快，利用双向链表维护访问顺序（修改节点位置快）。

class LRUCache {
    // 定义双向链表节点
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) { key = _key; value = _value; }
    }
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail; // 虚拟头尾节点，简化边界判断
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        // 访问后移到头部（表示最近使用过）
        moveToHead(node);
        return node.value;
    }
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超容，移除尾部节点（最久未使用）
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
    // 链表操作工具方法
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

2. 架构师思维：Redis 淘汰策略与并发安全

• 面试官追问：“Redis 里的 maxmemory-policy 有哪些？你的代码实现了哪种？在多线程环境下这个 LRU 安全吗？”
• 架构视角解析：
  • 策略对应：你的代码实现了 allkeys-lru 策略。但在生产环境中，Redis 还支持 volatile-lru（只淘汰设置了过期时间的）、LFU（最不经常使用）等。在缓存预热或热点数据场景下，LRU 可能会被“污染”，需要结合业务场景选择策略。
  • 并发问题：上述 Java 代码在多线程环境下是不安全的。如果用 ConcurrentHashMap 配合 synchronized 锁住链表操作，性能会下降。
  • 高性能方案：真正的架构师会想到 ConcurrentHashMap 的分段锁思想，或者使用 LinkedBlockingDeque。而在 Redis 单线程模型中，它不需要考虑线程安全问题，这也是 Redis 极快的原因之一。如果你在做高并发项目（如短视频秒杀），这里的锁粒度设计就是优化关键。

总结

算法题不仅仅是智力游戏，它是软件工程复杂度的微缩模型。

• 复杂链表复制 考验你对内存布局的敏感度；
• 二叉树转链表 考验你对数据索引的理解；
• LRU 缓存 考验你对性能与空间的权衡。 当你能用架构师的视角去拆解这些题目时，代码就不再是冰冷的字符，而是系统设计的蓝图。祝你在面试中不仅能解出题目，更能展现出令人印象深刻的技术深度！