数据结构与算法之 LeetCode：面试必刷 100 题（核心题型 / 解题思路）
在当今的软件开发领域，数据结构与算法是程序员必须掌握的核心技能。LeetCode 作为全球知名的在线编程挑战平台，提供了大量的编程题目，涵盖了从基础到高级的各种题型。本文将围绕 LeetCode 上的 100 道面试必刷题，分析其核心题型和解题思路，帮助读者在面试中脱颖而出。
一、核心题型分析
LeetCode 上的题目可以分为以下几类核心题型：
1. 数组与矩阵
2. 链表
3. 栈与队列
4. 树与图
5. 动态规划
6. 贪心算法
7. 深度优先搜索（DFS）
8. 广度优先搜索（BFS）
9. 双指针
10. 位操作
以下将针对这些题型进行详细解析。
二、数组与矩阵
题型特点
数组与矩阵题目通常涉及数组的遍历、查找、排序等操作，以及矩阵的变换、旋转等。
经典题目
1. 两数之和（LeetCode 1）
- 解题思路：使用哈希表存储数组元素的值和索引，遍历数组时检查目标值是否存在于哈希表中。
2. 三数之和（LeetCode 15）
- 解题思路：排序数组后，使用双指针遍历数组，找到和为 0 的三个数。
代码示例
python
def twoSum(nums, target):
num_dict = {}
for i, num in enumerate(nums):
if target - num in num_dict:
return [num_dict[target - num], i]
num_dict[num] = i
三、链表
题型特点
链表题目主要考察链表的创建、遍历、反转、删除等操作。
经典题目
1. 反转链表（LeetCode 206）
- 解题思路：使用三个指针，依次遍历链表，实现反转。
2. 合并两个有序链表（LeetCode 21）
- 解题思路：创建一个哑节点，遍历两个链表，比较节点值，将较小的节点连接到哑节点上。
代码示例
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
prev, curr = None, head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
四、栈与队列
题型特点
栈与队列题目主要考察栈和队列的基本操作，以及它们在特定问题中的应用。
经典题目
1. 有效的括号（LeetCode 20）
- 解题思路：使用栈存储括号，遍历字符串，遇到左括号入栈，遇到右括号出栈，比较栈顶元素。
2. 最小栈（LeetCode 155）
- 解题思路：使用两个栈，一个存储元素，一个存储元素的最小值。
代码示例
python
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
self.stack.pop()
五、树与图
题型特点
树与图题目主要考察树和图的基本操作，以及它们在路径搜索、拓扑排序等场景中的应用。
经典题目
1. 二叉树的遍历（LeetCode 94）
- 解题思路：递归或迭代实现前序、中序、后序遍历。
2. 拓扑排序（LeetCode 207）
- 解题思路：使用 BFS 或 DFS 进行拓扑排序。
代码示例
python
def inorderTraversal(root):
if not root:
return []
return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
六、动态规划
题型特点
动态规划题目通常需要找到子问题的最优解，并利用这些子问题的解来构建原问题的解。
经典题目
1. 最长递增子序列（LeetCode 300）
- 解题思路：使用动态规划，记录以每个元素结尾的最长递增子序列的长度。
2. 打家劫舍（LeetCode 198）
- 解题思路：使用动态规划，记录到当前位置为止的最大偷窃金额。
代码示例
python
def lengthOfLIS(nums):
if not nums:
return 0
dp = [1] len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
七、贪心算法
题型特点
贪心算法题目通常需要找到局部最优解，并期望这些局部最优解能够构成全局最优解。
经典题目
1. 打家劫舍 II（LeetCode 213）
- 解题思路：贪心选择当前最大值，同时避免选择相邻的房屋。
2. 最小路径和（LeetCode 64）
- 解题思路：贪心选择当前最小值，同时避免选择相邻的单元格。
代码示例
python
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
return max(rob(nums[:-1]), rob(nums[1:]))
八、深度优先搜索（DFS）与广度优先搜索（BFS）
题型特点
DFS 和 BFS 是两种常用的图遍历算法，适用于路径搜索、拓扑排序等问题。
经典题目
1. 二叉树的层序遍历（LeetCode 102）
- 解题思路：使用 BFS 遍历二叉树的每一层。
2. 单词搜索（LeetCode 79）
- 解题思路：使用 DFS 在图中搜索路径。
代码示例
python
from collections import deque
def levelOrder(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
九、双指针
题型特点
双指针题目通常需要使用两个指针遍历数组或链表，找到满足条件的元素。
经典题目
1. 移除元素（LeetCode 27）
- 解题思路：使用两个指针，一个指向当前元素，一个指向下一个元素，遍历数组。
2. 两数之和 II - 输入有序数组（LeetCode 167）
- 解题思路：使用两个指针，一个指向数组的开始，一个指向数组的结束，遍历数组。
代码示例
python
def removeElement(nums, val):
left, right = 0, len(nums) - 1
while left <= right:
if nums[left] == val:
nums[left], nums[right] = nums[right], nums[left]
right -= 1
else:
left += 1
return left
十、位操作
题型特点
位操作题目主要考察位运算符的应用，如按位与、按位或、按位异或、左移、右移等。
经典题目
1. 整数反转（LeetCode 7）
- 解题思路：使用位运算符实现整数的反转。
2. 只出现一次的数字（LeetCode 136）
- 解题思路：使用异或运算符找到只出现一次的数字。
代码示例
python
def reverse(x):
res = 0
while x != 0:
pop = x % 10
x //= 10
if res > 231 // 10 or (res == 231 // 10 and pop > 7):
return 0
if res < -231 // 10 or (res == -231 // 10 and pop < -8):
return 0
res = res 10 + pop
return res
总结
本文围绕 LeetCode 上的 100 道面试必刷题，分析了核心题型和解题思路。通过学习这些题目，读者可以巩固数据结构与算法的基础知识，提高编程能力。在面试中，掌握这些核心题型和解题思路将有助于应对各种面试挑战。
Comments NOTHING