LeetCode 简单难度

在 LeetCode 面试中,简单题 主要考察基础的数据结构、算法思想和编程能力.你可以从分类和方法论两个角度来总结.

1. 常见题型分类

1. 数组与哈希表

1. 常见题型
   • 两数之和 (Two Sum)
   • 存在重复元素 (Contains Duplicate)
   • 移除重复元素 (Remove Duplicates)
2. 方法论
   • 哈希表(HashMap / Set)优化查找,提升查询效率到 O(1)
   • 双指针法 处理排序数组,减少不必要的遍历
3. 时间复杂度:
   • 遍历数组 O(n),哈希表插入查询 O(1)

2. 字符串

1. 常见题型
   • 反转字符串 (Reverse String)
   • 验证回文串 (Valid Palindrome)
   • 字符串中的第一个唯一字符 (First Unique Character in a String)
2. 方法论
   • 双指针法 处理回文问题(从两端向中间移动)
   • 哈希表计数 统计字符频次,快速查找唯一字符
   • 滑动窗口 处理子串问题
3. 时间复杂度:
   • 遍历字符串 O(n),哈希表操作 O(1)

3. 链表

1. 常见题型:
   • 反转链表 (Reverse Linked List)
   • 合并两个有序链表 (Merge Two Sorted Lists)
   • 删除链表中的节点 (Remove Linked List Elements)
2. 方法论:
   • 双指针遍历 链表
   • 递归 处理反转问题
   • 哑节点技巧 统一插入/删除逻辑
3. 时间复杂度:
   • 遍历链表 O(n)

4. 栈与队列

1. 常见题型:
   • 有效的括号 (Valid Parentheses)
   • 用栈实现队列 (Implement Queue using Stacks)
   • 最小栈 (Min Stack)
2. 方法论:
   • 栈(LIFO) 适合匹配问题(如括号匹配)
   • 队列(FIFO) 适合按顺序处理问题
   • 双栈实现队列(一个输入栈、一个输出栈)
3. 时间复杂度:
   • 入栈/出栈 O(1)
   • 平摊复杂度 O(1) 的双栈队列

5. 二叉树(基础遍历)

1. 常见题型:
   • 二叉树的前序/中序/后序遍历 (Binary Tree Traversal)
   • 二叉树的最大深度 (Maximum Depth of Binary Tree)
   • 对称二叉树 (Symmetric Tree)
2. 方法论:
   • 递归 DFS 处理遍历问题
   • 队列 BFS 适合层序遍历
   • 栈模拟递归 用于非递归遍历
3. 时间复杂度:
   • 遍历树 O(n),每个节点访问一次

6. 二分查找

1. 常见题型:
   • 二分查找 (Binary Search)
   • 猜数字大小 (Guess Number Higher or Lower)
2. 方法论:
   • 二分法 适用于有序数组查找
   • 左闭右开区间 vs 左闭右闭区间 细节实现要注意
3. 时间复杂度:
   • O(log n)

7. 排序

1. 常见题型:
   • 合并两个有序数组 (Merge Sorted Array)
   • 数组中的第 K 大元素 (Kth Largest Element in an Array)
2. 方法论:
   • 双指针合并排序数组
   • 快速排序/堆排序
3. 时间复杂度:
   • 归并 O(n),快排 O(n log n)

2. 方法论总结

1. 哈希表优化查找:适用于唯一元素查找、频次统计,时间复杂度降至 O(1).
2. 双指针法:适用于排序数组、链表、字符串回文问题.
3. 递归 vs 迭代:二叉树遍历、链表反转要灵活运用递归和迭代.
4. 二分查找:针对有序数组查找问题,时间复杂度降至 O(\log n).
5. 栈和队列:匹配问题用栈,层次遍历用队列,双栈模拟队列操作.
6. 滑动窗口:适用于子串、子数组问题,如最长无重复子串.