第30章：综合实战——多算法融合、系统设计思维、经典例题

终于到了最后一章。说实话，写到这里我有点感慨。

前面29章，我们拆解了各种算法模式——二分、回溯、DP、图论……但现实中的问题，从来不会贴个标签告诉你「我用动态规划」。真正的工程难题，往往是多种算法的组合拳。

今天我们就拿两个经典题目来练手：设计Twitter 和 单词搜索II。一个偏系统设计，一个偏算法融合。你想想看，这两个题恰好代表了面试中的两个极端——一个考你架构能力，一个考你代码功底。

30.1 单词搜索II：Trie + 回溯的经典组合

先讲单词搜索II。这题我当年在面试Google时遇到过，当时差点翻车。

题目很简单：给你一个字符矩阵，再给你一堆单词，找出所有能在矩阵中拼出来的单词。你可以上下左右走，不能重复用同一个格子。

最笨的办法是什么？对每个单词做一次DFS。但如果有1000个单词，矩阵是12x12，那复杂度就炸了——O(N * M * 4^L)，N是单词数，L是单词长度。

我当时第一反应也是这么干，写到一半突然意识到不对。面试官看了我一眼，说：「你想想，有没有办法复用搜索路径？」

嗯，这就是关键——Trie树。

说白了，就是把「对每个单词单独搜索」变成了「一次搜索匹配所有单词」。Trie在这里起到了字典加速的作用。

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = null;  // 存储完整单词，方便回溯时收集结果
}

class Solution {
    List<String> result = new ArrayList<>();
    
    public List<String> findWords(char[][] board, String[] words) {
        // 1. 建Trie
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new TrieNode();
                }
                node = node.children[idx];
            }
            node.word = w;
        }
        
        // 2. 对每个格子做DFS
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root);
            }
        }
        return result;
    }
    
    void dfs(char[][] board, int i, int j, TrieNode node) {
        char c = board[i][j];
        if (c == '#' || node.children[c - 'a'] == null) return;
        
        node = node.children[c - 'a'];
        if (node.word != null) {
            result.add(node.word);
            node.word = null;  // 防止重复添加
        }
        
        board[i][j] = '#';  // 标记已访问
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        for (int[] d : dirs) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
                dfs(board, ni, nj, node);
            }
        }
        board[i][j] = c;  // 回溯恢复
    }
}

这里有个坑要注意——重复单词。如果矩阵里同一个单词出现多次，你只应该返回一次。我一开始没加 node.word = null 这行，结果结果集里一堆重复。嗯，这种小细节，debug起来挺烦的。

30.2 设计Twitter：系统设计中的算法思维

接下来这个题，很多人觉得是系统设计，跟算法没关系。其实不然。

设计Twitter的核心功能：

• 用户发推
• 用户关注/取关
• 获取用户的时间线（自己发的 + 关注的人发的，按时间倒序）
• 获取热点新闻流（这个我们简化，先不做）

你想想看，如果让你用纯SQL做，怎么查「我关注的所有人的最近10条推文」？

嗯，JOIN + ORDER BY + LIMIT。但如果关注了1000个人，每人发了10000条推文，这个查询就慢了。

这时候，算法就派上用场了——多路归并。

说白了，这就是合并K个有序链表的变体。你看，算法模式又出现了。

class Twitter {
    // 用户 - 推文链表（用LinkedList模拟，头插法保证最新在前）
    Map<Integer, LinkedList<Tweet>> tweets;
    // 用户 - 关注列表
    Map<Integer, Set<Integer>> follows;
    int timestamp = 0;
    
    class Tweet {
        int id, time;
        Tweet(int id) { this.id = id; this.time = timestamp++; }
    }
    
    public Twitter() {
        tweets = new HashMap<>();
        follows = new HashMap<>();
    }
    
    public void postTweet(int userId, int tweetId) {
        tweets.putIfAbsent(userId, new LinkedList<>());
        tweets.get(userId).addFirst(new Tweet(tweetId));
    }
    
    public void follow(int followerId, int followeeId) {
        follows.putIfAbsent(followerId, new HashSet<>());
        follows.get(followerId).add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        if (follows.containsKey(followerId)) {
            follows.get(followerId).remove(followeeId);
        }
    }
    
    public List<Integer> getNewsFeed(int userId) {
        // 多路归并：用最大堆，按时间戳排序
        PriorityQueue<Tweet> heap = new PriorityQueue<>(
            (a, b) -> b.time - a.time
        );
        
        // 把自己加进去
        if (tweets.containsKey(userId)) {
            heap.addAll(tweets.get(userId));
        }
        
        // 把关注的人加进去
        Set<Integer> followees = follows.getOrDefault(userId, new HashSet<>());
        for (int f : followees) {
            if (tweets.containsKey(f)) {
                heap.addAll(tweets.get(f));
            }
        }
        
        // 取前10条
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < 10 && !heap.isEmpty(); i++) {
            res.add(heap.poll().id);
        }
        return res;
    }
}

30.3 知识体系总览

这两个题，其实代表了算法学习的两个方向：

• 单词搜索II：数据结构（Trie）+ 搜索算法（回溯/DFS）的融合
• 设计Twitter：系统设计 + 经典算法模式（多路归并）的结合

我个人的体会是，面试到了高级阶段，考的不是你会不会背模板，而是你能不能把学过的模式灵活组合。就像乐高积木，单个模块谁都会拼，但能搭出复杂结构才是真本事。

30.4 核心逻辑流程图

下面这张图，把本章两个题的核心逻辑串在了一起。你看，左边是单词搜索II的Trie+回溯流程，右边是Twitter的多路归并流程。它们底层都依赖同一个思想——用高效的数据结构减少搜索空间。

30.5 写在最后

30章，从基础的数据结构到高级算法模式，从理论分析到实战应用，我们走了一段不短的路。

我记得刚开始写这个课程时，就在想——到底什么样的内容对读者最有价值？后来我想明白了：不是堆砌知识点，而是帮你建立「算法直觉」。看到一个问题，能快速判断出它属于哪类模式，能用什么数据结构优化，边界条件在哪里。

这种直觉，靠背是背不出来的。得多练，多总结，多踩坑。

嗯，课程到这里就结束了。但你的算法之路，才刚刚开始。

加油，我们江湖再见。