LeetCode 中等难度

在 LeetCode 中等难度 题目中,考察的核心是 数据结构、算法优化和问题建模能力.你需要掌握高效的算法技巧,以 降低时间复杂度 并 优化空间使用.

1. 常见题型分类

1. 数组 & 前缀和 & 滑动窗口

1. 常见题型: • 前缀和:和为 K 的子数组 (Subarray Sum Equals K) • 滑动窗口:无重复字符的最长子串 (Longest Substring Without Repeating Characters) • 双指针+贪心:三数之和 (3Sum)
2. 方法论: • 前缀和 + 哈希表 预存和减少查询时间 • 滑动窗口 适合处理连续子数组问题 • 双指针 适合求和、去重问题
3. 时间复杂度: • 前缀和/哈希表:O(n) • 滑动窗口:O(n) • 双指针排序后 O(n \log n) ,遍历 O(n)

2. 二分查找 & 二分答案

1. 常见题型: • 标准二分:搜索旋转排序数组 (Search in Rotated Sorted Array) • 二分答案:最小的 K 个数 (Kth Smallest Element in a Sorted Matrix)
2. 方法论: • 标准二分:二分边界问题,注意左闭右闭 / 左闭右开区别 • 二分答案:用于求最优解(如最小可行值)
3. 时间复杂度: • 标准二分查找:O(\log n) • 二分答案(例如矩阵二分):O(n \log m)

3. 链表

1. 常见题型: • 双指针:环形链表 (Linked List Cycle) • 归并排序:合并 K 个有序链表 (Merge K Sorted Lists)
2. 方法论: • 快慢指针 解决环形问题 • 堆(优先队列)+ 归并 处理多个链表合并
3. 时间复杂度: • 双指针:O(n) • 堆归并排序:O(n \log k)

4. 栈 & 单调栈

1. 常见题型: • 单调栈:每日温度 (Daily Temperatures) • 单调栈:柱状图中的最大矩形 (Largest Rectangle in Histogram)
2. 方法论: • 单调栈 用于维护递增/递减序列,快速计算区间值
3. 时间复杂度: • 单调栈:O(n)

5. 哈希表 & 位运算

1. 常见题型: • 异或:只出现一次的数字 (Single Number II) • 哈希表:字母异位词 (Group Anagrams)
2. 方法论: • 位运算(异或) 解决数字出现次数问题 • 哈希表 处理高效查找
3. 时间复杂度: • 哈希表存取:O(1) • 位运算:O(n)

6. 树 & DFS/BFS

1. 常见题型: • 二叉搜索树(BST):二叉搜索树中第 K 小的元素 (Kth Smallest Element in a BST) • BFS:二叉树的右视图 (Binary Tree Right Side View)
2. 方法论: • 递归 DFS 用于遍历树结构 • 队列 BFS 适合层序遍历
3. 时间复杂度: • DFS/BFS 遍历树:O(n) • 二叉搜索树查找:O(\log n)

7. 动态规划(DP)

1. 常见题型: • 经典 DP:爬楼梯 (Climbing Stairs) • 区间 DP:戳气球 (Burst Balloons)
2. 方法论: • 状态转移方程 定义子问题 • 记忆化搜索 解决重复子问题
3. 时间复杂度: • 递推 DP:O(n) • 区间 DP:O(n^2)

8. 图 & 拓扑排序

1. 常见题型: • 最短路径:网络延迟时间 (Network Delay Time) • 拓扑排序:课程表 (Course Schedule)
2. 方法论: • Dijkstra / Bellman-Ford 计算最短路径 • 拓扑排序 解决依赖关系
3. 时间复杂度: • Dijkstra:O(E \log V) • 拓扑排序:O(V + E)

2. 方法论总结

1. 前缀和 / 滑动窗口:处理子数组问题,减少暴力求解的复杂度.
2. 二分答案:用于最优化问题,如「求最小满足条件的值」.
3. 双指针:高效处理排序数组或链表问题.
4. 单调栈:在区间问题中用于高效维护最大/最小值.
5. DFS / BFS:用于遍历树、图,并处理路径搜索问题.
6. 动态规划(DP):识别子问题,使用递推或记忆化搜索优化复杂度.
7. 拓扑排序:用于任务调度、依赖关系问题.