LeetCode高频算法精讲：大厂面试知识体系完全指南

算法面试是互联网大厂招聘的核心环节，掌握高频题型和解题模板是通关关键。本文系统讲解LeetCode上的五大高频题型：二分查找、滑动窗口、DFS/BFS、动态规划和贪心算法。每种算法包含原理讲解、标准模板、变体应对和复杂度分析，配合大量完整代码示例和详细注释，帮助读者建立完整的算法知识体系，从容应对各类面试挑战。

第一章 二分查找：搜索的艺术

二分查找是算法竞赛和面试中出现频率最高的算法之一。其核心思想是利用数据的有序性，通过每次比较排除一半的搜索空间，将时间复杂度从O(n)降低到O(log n)。虽然思想简单，但边界条件的正确处理是面试官重点考察的内容。

1.1 核心原理与模板框架

二分查找的本质是通过折半缩小搜索范围。其核心框架包含四个关键要素：初始化左右边界、循环条件、中点计算、边界更新。不同的边界条件设置对应不同的应用场景。

# 二分查找标准模板 - 查找精确目标
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # 防止整数溢出
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

# 左边界模板 - 查找第一个等于target的位置
def left_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
if left < len(nums) and nums[left] == target:
return left
return -1

# 右边界模板 - 查找最后一个等于target的位置
def right_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
if right > 0 and nums[right-1] == target:
return right - 1
return -1

1.2 经典题型与变体分析

二分查找的变体主要围绕搜索空间和目标定义展开。常见的变体包括：搜索插入位置、搜索旋转数组、搜索峰值元素、搜索矩阵等。

第二章 滑动窗口：子数组问题的最优解

滑动窗口是解决连续子数组/子串问题的利器。核心思想是维护一个可变窗口，通过左右指针的移动来调整窗口范围。其时间复杂度通常为O(n)，显著优于暴力解法的O(n^2)。

2.1 固定窗口模板

# 固定窗口大小k，求最大和
def max_sum_subarray(nums, k):
if len(nums) < k:
return 0
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i-k]
max_sum = max(max_sum, window_sum)
return max_sum

# 固定窗口求平均数
def max_average(nums, k):
window_sum = sum(nums[:k])
max_avg = window_sum / k
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i-k]
max_avg = max(max_avg, window_sum / k)
return max_avg

2.2 可变窗口模板

# 最小覆盖子串（LeetCode 76）
from collections import Counter

def min_window(s, t):
need = Counter(t)
window = Counter()
left = valid = 0
min_len = float('inf')
start = 0

for right, c in enumerate(s):
if c in need:
window[c] += 1
if window[c] == need[c]:
valid += 1

while valid == len(need):
if right - left + 1 < min_len:
start = left
min_len = right - left + 1

d = s[left]
left += 1
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1

return s[start:start+min_len] if min_len != float('inf') else ""

# 无重复字符的最长子串
def length_of_longest_substring(s):
window = set()
left = max_len = 0
for right, c in enumerate(s):
while c in window:
window.remove(s[left])
left += 1
window.add(c)
max_len = max(max_len, right - left + 1)
return max_len

第三章 DFS/BFS：图论基础与遍历策略

深度优先搜索（DFS）和广度优先搜索（BFS）是图论算法的基础。DFS适用于路径查找、连通性判断等场景；BFS适用于最短路径、层级遍历等场景。两者各有优劣，需要根据问题特性选择。

3.1 DFS递归与迭代实现

# DFS递归：岛屿数量（LeetCode 200）
def num_islands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
count = 0

def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n:
return
if grid[i][j] == '0':
return
grid[i][j] = '0'
dfs(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i, j-1)

for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count

# DFS迭代：全排列
def permute(nums):
result = []
stack = [(nums, [])]
while stack:
remaining, path = stack.pop()
if not remaining:
result.append(path)
continue
for i in range(len(remaining)):
stack.append((remaining[:i]+remaining[i+1:], path+[remaining[i]]))
return result

3.2 BFS最短路径

from collections import deque

# BFS：最短路径（LeetCode 1091）
def shortest_path_binary_matrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1

q = deque([(0, 0, 1)])
visited = {(0, 0)}
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

while q:
r, c, dist = q.popleft()
if r == n-1 and c == n-1:
return dist
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in visited:
visited.add((nr, nc))
q.append((nr, nc, dist + 1))
return -1

第四章 动态规划：最优子结构与状态转移

动态规划是算法面试的核心难点。其核心思想是将复杂问题分解为重叠子问题，通过状态转移方程递推求解。常见的DP类型包括：背包问题、最长递增子序列、最长公共子序列、编辑距离等。

4.1 背包问题系列

# 0-1背包
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, capacity+1):
if weights[i-1] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
return dp[n][capacity]

# 完全背包（物品可重复使用）
def complete_knapsack(weights, values, capacity):
dp = [0]*(capacity+1)
for i in range(len(weights)):
for j in range(weights[i], capacity+1):
dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
return dp[capacity]

4.2 经典DP问题

第五章 贪心算法：局部最优的选择策略

贪心算法在每一步选择中都采取当前最优的选择，期望最终达到全局最优。虽然不总能得到最优解，但在特定问题上非常高效，如区间调度、跳跃游戏等。

# 跳跃游戏（LeetCode 55）
def can_jump(nums):
max_reach = 0
for i, num in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + num)
if max_reach >= len(nums) - 1:
return True
return max_reach >= len(nums) - 1

# 区间调度（LeetCode 435）
def erase_overlap_intervals(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[1])
count = 0
end = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] < end:
count += 1
else:
end = intervals[i][1]
return count

第六章 大厂面试高频题分布统计