️ 一、 哈希表O(1) 神话的缔造者与冲突解决1. 哈希表的原理是什么哈希表Hash Table是一种通过哈希函数把键key映射到数组下标从而在平均 O(1) 时间内完成查找、插入、删除的数据结构。核心原理四步走准备一个固定大小的数组作为“桶数组”。用哈希函数hash(key)把键映射成一个整数。用这个整数对数组长度取模或位运算得到桶下标。把键值对放到这个桶里。2. 哈希冲突怎么解决不同的 key 经过哈希函数后可能映射到同一个下标这就是哈希冲突无法完全避免。主要有两大解决方案链地址法拉链法每个桶里挂一个链表或红黑树冲突的元素都挂在对应桶的链表上。Java HashMap 和 Redis 的 dict 都用这种方式。注意点JDK 1.8 之后当某个桶的链表长度 ≥ 8 且数组长度 ≥ 64 时链表会转成红黑树进一步优化最坏情况下的查找。开放寻址法冲突时按一定规则在数组里寻找下一个空位。常见探测方式有线性探测i, i1, i2...、二次探测i, i1², i2²...、双重哈希。Java 的ThreadLocalMap就是用线性探测。3. 负载因子Load Factor公式元素数量 / 桶数量。负载因子越大冲突越多。Java HashMap 默认 0.75超过就触发扩容rehash以维持平均 O(1) 的查找性能。 二、 归并排序分治思想的完美体现1. 原理与实现归并排序是一种典型的分治算法思想非常清晰就是“分、治、合”三步分把数组从中间一分为二分到底。治递归地对两半分别排序。合把两个已排序的子数组合并成一个有序数组。2. 复杂度与特性时间复杂度最好、最坏、平均都是O(n log n)共 log n 层递归每层合并总共处理 n 个元素。空间复杂度O(n)需要额外的临时数组存放合并结果。稳定性稳定排序合并时相同元素按原始顺序放入。3. 对比快排与应用场景相比快排的优势稳定、最坏情况也是 O(n log n)快排最坏是 O(n²)。相比快排的劣势需要 O(n) 额外空间不是原地排序。典型应用场景外部排序内存放不下的海量数据。链表排序对链表非常友好空间可以做到 O(1)。需要稳定性的业务场景。#include iostream #include vector // 合并两个有序子数组 void merge(vectorint arr, int left, int mid, int right) { vectorint temp(right - left 1); int i left, j mid 1, k 0; while (i mid j right) { // 注意这里用 保证稳定性 if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; // 将临时数组拷贝回原数组 for (int p 0; p k; p) { arr[left p] temp[p]; } } void mergeSort(vectorint arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); // 递归排序左半 mergeSort(arr, mid 1, right); // 递归排序右半 merge(arr, left, mid, right); // 合并 }三、 二分查找思路很简单细节是魔鬼1. 核心思想与标准实现二分查找是对有序数组进行查找的经典算法时间复杂度 O(log n)。核心思想是每次比较中间元素根据大小关系把查找范围缩小一半。2. 容易踩的坑整数溢出不要写(left right) / 2当left和right都接近Integer.MAX_VALUE时会溢出必须写成left (right - left) / 2。边界区间的写法要统一闭区间[left, right]循环条件left right更新时left mid 1或right mid - 1。左闭右开[left, right)循环条件left right更新时left mid 1或right mid不减 1。⚠️两种写法不能混用否则要么死循环要么漏解。死循环如果循环里某个分支忘记让left或right变化会导致死循环。变体题查找“第一个等于 target”、“最后一个等于 target”、“第一个大于等于 target”等变体需要小心和的取舍。#include vector int binarySearch(const vectorint arr, int target) { int left 0, right arr.size() - 1; // 闭区间 [left, right] while (left right) { // 防溢出写法面试必考 int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; // 更新左边界 } else { right mid - 1; // 更新右边界 } } return -1; // 未找到 }四、 DFS 与 BFS图/树遍历的双子星1. 区别与实现DFS深度优先一条路走到黑走不通再回溯。通常用递归或栈实现。BFS广度优先一层一层向外扩展。通常用队列实现。2. 对比表格维度DFSBFS实现递归 / 栈队列空间复杂度O(h)h 是递归栈深度树的高度O(w)w 是树最宽一层的节点数能否求最短路径不能直接求可以边权相等的图BFS 第一次到达即最短路径典型应用全排列、子集、拓扑排序、检测环、连通分量、回溯层序遍历、求最短路径、“最少几步”类问题3. 经典题举例二叉树前/中/后序遍历 → DFS二叉树层序遍历 → BFSLeetCode 200 岛屿数量 → DFS/BFS 都行LeetCode 994 腐烂的橘子求最短感染时间 → BFS回溯类题目全排列、N 皇后、子集、组合 → DFS 一句话区别要找最短路径、最少步数用 BFS要穷举所有方案或深挖某条路径用 DFS。五、 链表手撕反转链表与环形链表1. 如何反转一个链表这是链表手撕题里最经典的一道要会两种解法。解法一迭代推荐O(1) 空间用三个指针prev、curr、next依次调转每个节点的指向。时间复杂度 O(n)空间复杂度 O(1)。struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr ! nullptr) { ListNode* nextTemp curr-next; // 暂存下一个节点 curr-next prev; // 反转当前节点指针 prev curr; // prev 前进 curr nextTemp; // curr 前进 } return prev; // 最后 prev 就是新的头节点 }解法二递归递归到最后一个节点作为新头节点然后在回溯的过程中改变指针指向。时间复杂度 O(n)但递归栈占用 O(n) 空间。⚠️一定要考虑空链表head null和只有一个节点的边界情况上面两种写法都已经处理了。ListNode* reverseListRecursive(ListNode* head) { // 边界情况空链表或只有一个节点 if (head nullptr || head-next nullptr) return head; ListNode* newHead reverseListRecursive(head-next); head-next-next head; // 让下一个节点的 next 指向当前节点 head-next nullptr; // 当前节点的 next 设为 null避免成环 return newHead; }2. 如何判断一个链表是否有环如何找到环的入口节点这是快慢指针Floyd 判圈算法的经典应用题两问都有标准答案。第一问判断有没有环用两个指针slow和fastslow每次走 1 步fast每次走 2 步。如果fast走到了null说明没有环如果fast追上了slow相遇说明有环。第二问找环的入口节点关键结论Floyd 算法的数学推导在slow和fast相遇后让其中一个指针回到链表头两个指针都每次走一步再次相遇的地方就是环的入口。数学原理设头到入口距离为a入口到相遇点为b相遇点到入口沿环走为c。相遇时slow a bfast a b k(b c)多跑了 k 圈。由fast 2 * slow推出a (k - 1)(b c) c含义就是从头走 a 步等价于从相遇点走 c 步再走若干整圈两者一定会同时到达入口。ListNode* detectCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { // 相遇开始找入口 ListNode* p head; while (p ! slow) { p p-next; slow slow-next; } return p; // 再次相遇的地方就是环的入口 } } return nullptr; // 无环 }六、 二叉树遍历四种方式一网打尽二叉树遍历分两大类DFS 三种和BFS 一种一共四种都是超高频考点。1. DFS 三种根据根节点被访问的顺序区分前序遍历根 → 左 → 右中序遍历左 → 根 → 右二叉搜索树的中序遍历结果是升序的后序遍历左 → 右 → 根递归实现以中序为例代码非常简洁牢记“左、根、右”的顺序递归调用即可。迭代实现需要显式用栈。#include stack vectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* stk; TreeNode* curr root; while (curr ! nullptr || !stk.empty()) { // 一路向左把左节点全部压栈 while (curr ! nullptr) { stk.push(curr); curr curr-left; } // 弹出栈顶最左节点并访问 curr stk.top(); stk.pop(); result.push_back(curr-val); // 转向右子树 curr curr-right; } return result; }2. BFS 一种层序遍历Level Order用队列实现一层一层访问。核心技巧是在每一层开始前记录当前队列的大小size然后用一个循环把当前层的节点全部处理完并将其子节点加入队列。这样就能完美分层输出。#include queue vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (root nullptr) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); // 记录当前层的节点数 vectorint level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(level); } return result; }七、什么是动态规划DP动态规划Dynamic Programming是一种把大问题拆解为重叠子问题、通过记录子问题的解来避免重复计算的算法思想。它本质上是“聪明的暴力枚举”。一个问题是能否用DP通常看两个特征最优子结构原问题的最优解可以由子问题的最优解组合而来。重叠子问题递归求解时会反复计算相同的子问题这正是DP比暴力递归快的原因。 掌握DP的解题套路核心四步曲定义状态dp[i]或dp[i][j]到底表示什么状态转移方程dp[i]如何从之前的状态推导出来初始化边界状态如何赋值遍历顺序是从前往后、从后往前还是按某种维度 进阶技巧必备先想暴力递归 - 发现重叠子问题 - 用数组/哈希表做记忆化搜索- 改写成自底向上的迭代DP- 最后用滚动数组优化空间。掌握这套流程80%的DP题都能套 实战斐波那契滚动数组空间优化以最基础的爬楼梯为例状态转移方程dp[i] dp[i-1] dp[i-2]。为了节省空间我们不用存整个数组只用两个变量。int climbStairs(int n) { if (n 2) return n; int prev2 1; // dp[1] int prev1 2; // dp[2] int current 0; for (int i 3; i n; i) { current prev1 prev2; prev2 prev1; prev1 current; } return current; }典型题目图谱0-1背包、完全背包零钱兑换、最长公共子序列LCS、最长递增子序列LIS、最长回文子串、编辑距离、打家劫舍贪心算法和动态规划有什么区别两者都用于求最优解问题但核心区别在于做决策时是否回头看。维度贪心算法动态规划决策方式每一步都做当前看起来最优的选择枚举所有可能的子问题解再做选择是否有后效性假设当前选择不影响未来基于之前所有状态推导正确性只在“贪心选择性质”成立时才能得到最优解只要状态转移方程定义对了一定能得到最优解时间复杂度通常更快O(n) 或 O(n log n)通常 O(n²) 或更高空间复杂度通常 O(1)通常 O(n) 或 O(n²)典型贪心题找零钱面值 1/5/10/25每次尽量用大面额。区间调度活动选择按结束时间排序依次选能加入的活动。霍夫曼编码每次合并频率最小的两个节点。跳跃游戏每一步都跳到“能到达的最远位置”。贪心是“每一步都走当前看起来最好的”DP是“把所有可能性都算过再选最好的”。贪心更快但不一定正确DP一定正确但更慢。