牛客网代码题算法学习大纲（通俗逻辑版）

• 数组 & 链表

  数组：像一排连续座位，支持快速随机访问（如找第5个人），但插入/删除需挪动元素（时间复杂度O(n)）。

  链表：像手拉手的队伍，插入/删除只需修改指针（时间复杂度O(1)），但查找需从头遍历（时间复杂度O(n)）。

  关键场景：数组适合静态数据，链表适合频繁增删的动态数据。

• 栈 & 队列

  栈：叠盘子，后进先出（LIFO），适合括号匹配、函数调用栈、DFS。

  队列：排队买奶茶，先进先出（FIFO），适合层序遍历、BFS、滑动窗口。

• 哈希表

  像快递柜，通过取件码（Key）直接找到包裹（Value），支持快速查重、统计频率（时间复杂度O(1)）。

• 字符串

  本质是字符数组，需注意拼接（可能超时）、子串匹配（如KMP算法通过跳过已匹配部分优化）。

• 树 & 二叉树

  树：家族结构，根节点到叶子是分支路径。

  二叉树：每个节点最多两个孩子，适合递归处理（如遍历、求深度）。

• 堆（优先队列）

  像跷跷板，总让最重（或最轻）元素在顶端，适合快速取Top K问题（如堆排序）。

• 图

  多个节点互相连接（如社交网络），需处理最短路径（Dijkstra）、连通性（并查集）等问题。

• 递归 & 分治

  递归：函数调用自身，需明确终止条件（如计算阶乘）。

  分治：大事化小（如归并排序：拆分→排序→合并）。

• 贪心算法

  每次选当前最优解（如选最大硬币），但可能错过全局最优（需问题允许贪心策略成立）。

• 回溯算法

  试错法：走迷宫遇到死路退回（如全排列：尝试所有可能后撤销选择）。

• 动态规划（DP）

  记住小问题结果，避免重复计算（如斐波那契数列、背包问题）。

• 双指针

  两人协作：一快一慢找链表环，或一左一右压缩搜索空间（如两数之和）。

• 滑动窗口

  伸缩窗口保持条件（如最长无重复子串、固定窗口和）。

• 前缀和 & 差分

  前缀和：提前计算累加值，快速求区间和（如子数组和问题）。

  差分：记录变化量，快速批量增减区间（如区间更新）。

• 位运算

  二进制技巧：异或找单身狗（相同数异或为0），掩码提取特定位。

• 搜索算法

  BFS：逐层扩散，适合找最短路径（如迷宫最短步数）。

  DFS：一条路走到底，适合遍历所有可能性（如迷宫所有出口）。

• 排序算法

  快速排序：选基准分左右，递归排序。

  归并排序：分治合并有序子数组。

  堆排序：建堆后交换堆顶与末尾元素。

• 链表操作

  反转链表（头插法或递归）、检测环（快慢指针）、合并有序链表。

• 二叉树问题

  遍历（前序/中序/后序）、求深度、判断对称、最近公共祖先。

• 子串 & 子序列

  最长公共子串（连续）、最长公共子序列（不连续）、回文子串（中心扩展或DP）。

• 排列组合

  全排列（回溯+去重）、组合总和（控制元素重复使用）。

• Top K问题

  用堆找最大/小的K个数，或快速选择算法（平均时间复杂度O(n)）。

• 数学问题

  质数判断、进制转换、随机数生成、概率问题（如抛硬币期望）。

• 设计类问题

  LRU缓存（哈希表+双向链表）、实现栈/队列等数据结构。

• 并查集

  处理连通性问题：合并集合、查找根节点（如朋友圈问题）。

• 字典树（Trie）

  高效存储字符串集合，快速判断前缀（如搜索提示）。

• 单调栈/队列

  维护有序结构：找下一个更大元素、滑动窗口最大值。

• 图算法

  最短路径（Dijkstra、Floyd）、拓扑排序（课程安排）、最小生成树（Prim/Kruskal）。

1. 阶段1：打基础

   掌握基础数据结构操作（增删改查）。

   理解排序、递归、双指针等简单算法逻辑。

2. 阶段2：练思想

   重点突破动态规划、回溯、贪心等核心思想。

   按类型刷题（如先刷完所有二叉树题）。

3. 阶段3：实战提升

   限时模拟真实面试，综合运用算法。

   总结高频题（如LRU、反转链表、爬楼梯）。

• 按类型刷：同类题对比找规律（如所有子串问题用滑动窗口）。
• 画图分析：用纸笔模拟执行过程（如递归树、链表指针变化）。
• 五毒神掌：隔几天重做错题，强化记忆。
• 控制时间：20分钟无思路直接看题解，避免死磕。

• ? 只刷题不总结：同类题反复错，需记录错题本。
• ? 死磕难题：先掌握常见题（如Medium）再挑战Hard。
• ? 忽视基础：链表都写不稳直接学DP，会导致根基不稳。

算法本质是“逻辑套路”，先理解问题模式（如看到子串想滑动窗口），再匹配工具（数据结构）和思想（如DP）。坚持按类型刷题，多画图、多复述思路，代码自然水到渠成！