第30章算法综合实战

课程目录第30章算法综合实战

第30章算法综合实战：LeetCode经典题目解析、面试高频题、算法竞赛入门、刷题策略与总结

终于到了最后一章。说实话，每次课程收尾我都有点感慨。这一章我们不学新算法，而是把前面29章的东西串起来，看看它们在实际场景中怎么用。

我个人习惯把算法学习分成三个阶段：看懂、会写、能变通。前两个阶段靠刷题，第三个阶段靠总结。今天我们就聊聊怎么走完这三步。

30.1 LeetCode经典题目解析：从暴力到最优

先看一道我面试时经常出的题——两数之和。别看它标着Easy，里面门道不少。

题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标。

最直接的想法是双重循环，时间复杂度O(n²)。但面试官不会满意。我当年第一次面试就栽在这上面——写了个暴力解，面试官问“能优化吗”，我愣了半天。

优化的核心是空间换时间。用哈希表记录已经遍历过的元素，这样每次查找就是O(1)：

// 最优解：哈希表法
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    // 这里用静态数组模拟哈希表，实际工程中建议用uthash
    static int result[2];
    // 简单起见，假设值范围已知，用数组模拟
    // 实际LeetCode中需要动态哈希
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        // 查找complement是否在哈希表中
        // ... 哈希查找逻辑
        result[0] = hash_index;
        result[1] = i;
        *returnSize = 2;
        return result;
    }
    *returnSize = 0;
    return NULL;
}

核心思路：遍历一次数组，把每个元素的值和下标存入哈希表。对于当前元素，检查 target - nums[i] 是否已经在哈希表中。如果在，就找到了答案。

为什么哈希表这么快？因为它把查找从O(n)降到了O(1)。我在项目中处理百万级数据时，这种优化往往能省下几秒甚至几分钟。

30.2 面试高频题：链表反转的三种写法

链表反转是面试高频题，我面过的人里，能一次写对的不超过三成。这里我分享三种写法，你根据情况选。

迭代法（最推荐）：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *curr = head, *next = NULL;
    while (curr != NULL) {
        next = curr->next;   // 保存下一个节点
        curr->next = prev;   // 反转指针
        prev = curr;         // 前移
        curr = next;         // 前移
    }
    return prev;
}

递归法（代码简洁，但理解有难度）：

struct ListNode* reverseListRecursive(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    struct ListNode* newHead = reverseListRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

我的建议：面试时优先写迭代法。递归虽然看起来高级，但容易在边界条件上翻车。我曾经在面试中写递归，结果栈溢出了——嗯，那场面挺尴尬的。

30.3 算法竞赛入门：时间就是一切

算法竞赛和面试刷题是两回事。竞赛更看重代码速度和调试效率。我参加过几次ACM，最大的体会是：

模板要熟：快速排序、二分查找、并查集这些，要能闭着眼写出来
STL要会用：C++选手有优势，但C语言选手也能用uthash、cJSON等库
读题要快：竞赛题往往有故事包装，要快速提取核心算法问题

举个例子，一道题说“小明在森林里迷路了，要找到最短路径”——说白了就是BFS或Dijkstra。别被故事绕进去。

避坑指南：我曾经在竞赛中花20分钟写了一个复杂的线段树，结果发现数据范围很小，暴力就能过。所以，先评估数据规模，再选算法。

30.4 刷题策略与总结：怎么刷才有效？

很多同学问我：“刷了200道题还是没感觉，怎么办？”我的回答是：你可能在无效刷题。

有效刷题应该遵循这个流程：

分类刷：按数据结构或算法类型刷，比如这周只刷链表，下周只刷树
三遍法：第一遍看题解理解思路，第二遍自己写，第三遍限时写
总结模板：每种题型总结一个代码模板，比如二分查找的左右边界处理
复盘错题：把做错的题标记，一周后再做一遍

下面这张图是我自己总结的刷题知识体系，你可以参考：

30.5 实战：一道题串起多个知识点

来看一道综合题——二叉树的层序遍历。这道题涉及：队列、二叉树、BFS、动态内存管理。

// 层序遍历：用队列实现BFS
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    // 结果数组，假设最多1000层
    int** result = malloc(1000 * sizeof(int*));
    *returnColumnSizes = malloc(1000 * sizeof(int));
    *returnSize = 0;
    
    // 队列实现
    struct TreeNode** queue = malloc(2000 * sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear) {
        int levelSize = rear - front;
        result[*returnSize] = malloc(levelSize * sizeof(int));
        (*returnColumnSizes)[*returnSize] = levelSize;
        
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = queue[front++];
            result[*returnSize][i] = node->val;
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
        (*returnSize)++;
    }
    
    free(queue);
    return result;
}

关键点：

队列的front和rear指针要维护好，别越界
每层节点数就是当前队列长度
动态分配内存时，记得释放

这道题我在实际项目中用过——解析JSON树形结构时，需要按层级输出。嗯，算法真的不只是面试用。

30.6 总结：算法学习的终点

学完这30章，你应该能感受到：算法不是背代码，而是培养解决问题的思维方式。

我做了十几年嵌入式开发，算法思维帮了我很多：

用哈希表快速查找传感器数据
用BFS规划机器人路径
用动态规划优化资源分配

最后送你一句话：算法是内功，语言是招式。内功深厚了，用什么语言都能写出好代码。

我的刷题建议：每天1-2道题，坚持3个月。不要贪多，重在理解。遇到不会的题，先想10分钟，再看题解。看懂了不算会，能自己写出来才算。

好了，课程到这里就结束了。希望这些内容对你有帮助。记住，算法这条路没有捷径，但有方法。用对方法，坚持下去，你一定能成为算法高手。

📚 课程目录