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

算法面试是互联网大厂招聘的核心环节掌握高频题型和解题模板是通关关键。本文系统讲解LeetCode上的五大高频题型二分查找、滑动窗口、DFS/BFS、动态规划和贪心算法。每种算法包含原理讲解、标准模板、变体应对和复杂度分析配合大量完整代码示例和详细注释帮助读者建立完整的算法知识体系从容应对各类面试挑战。第一章 二分查找搜索的艺术二分查找是算法竞赛和面试中出现频率最高的算法之一。其核心思想是利用数据的有序性通过每次比较排除一半的搜索空间将时间复杂度从O(n)降低到O(log n)。虽然思想简单但边界条件的正确处理是面试官重点考察的内容。1.1 核心原理与模板框架二分查找的本质是通过折半缩小搜索范围。其核心框架包含四个关键要素初始化左右边界、循环条件、中点计算、边界更新。不同的边界条件设置对应不同的应用场景。# 二分查找标准模板 - 查找精确目标def binary_search(nums, target):left, right 0, len(nums) - 1while left right:mid left (right - left) // 2 # 防止整数溢出if nums[mid] target:return midelif nums[mid] target:left mid 1else:right mid - 1return -1# 左边界模板 - 查找第一个等于target的位置def left_bound(nums, target):left, right 0, len(nums)while left right:mid left (right - left) // 2if nums[mid] target:right midelse:left mid 1if left len(nums) and nums[left] target:return leftreturn -1# 右边界模板 - 查找最后一个等于target的位置def right_bound(nums, target):left, right 0, len(nums)while left right:mid left (right - left) // 2if nums[mid] target:left mid 1else:right midif right 0 and nums[right-1] target:return right - 1return -11.2 经典题型与变体分析二分查找的变体主要围绕搜索空间和目标定义展开。常见的变体包括搜索插入位置、搜索旋转数组、搜索峰值元素、搜索矩阵等。题型难度核心技巧时间复杂度空间复杂度精确查找Easy标准模板O(log n)O(1)左边界Medium收缩右边界O(log n)O(1)右边界Medium收缩左边界O(log n)O(1)旋转数组Hard分段二分O(log n)O(1)峰值查找Medium梯度判断O(log n)O(1)矩阵搜索Medium二维转一维O(log(mn))O(1)第二章 滑动窗口子数组问题的最优解滑动窗口是解决连续子数组/子串问题的利器。核心思想是维护一个可变窗口通过左右指针的移动来调整窗口范围。其时间复杂度通常为O(n)显著优于暴力解法的O(n^2)。2.1 固定窗口模板# 固定窗口大小k求最大和def max_sum_subarray(nums, k):if len(nums) k:return 0window_sum sum(nums[:k])max_sum window_sumfor 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 / kfor i in range(k, len(nums)):window_sum nums[i] - nums[i-k]max_avg max(max_avg, window_sum / k)return max_avg2.2 可变窗口模板# 最小覆盖子串LeetCode 76from collections import Counterdef min_window(s, t):need Counter(t)window Counter()left valid 0min_len float(inf)start 0for right, c in enumerate(s):if c in need:window[c] 1if window[c] need[c]:valid 1while valid len(need):if right - left 1 min_len:start leftmin_len right - left 1d s[left]left 1if d in need:if window[d] need[d]:valid - 1window[d] - 1return s[start:startmin_len] if min_len ! float(inf) else # 无重复字符的最长子串def length_of_longest_substring(s):window set()left max_len 0for right, c in enumerate(s):while c in window:window.remove(s[left])left 1window.add(c)max_len max(max_len, right - left 1)return max_len第三章 DFS/BFS图论基础与遍历策略深度优先搜索DFS和广度优先搜索BFS是图论算法的基础。DFS适用于路径查找、连通性判断等场景BFS适用于最短路径、层级遍历等场景。两者各有优劣需要根据问题特性选择。3.1 DFS递归与迭代实现# DFS递归岛屿数量LeetCode 200def num_islands(grid):if not grid:return 0m, n len(grid), len(grid[0])count 0def dfs(i, j):if i 0 or i m or j 0 or j n:returnif grid[i][j] 0:returngrid[i][j] 0dfs(i1, j)dfs(i-1, j)dfs(i, j1)dfs(i, j-1)for i in range(m):for j in range(n):if grid[i][j] 1:dfs(i, j)count 1return count# DFS迭代全排列def permute(nums):result []stack [(nums, [])]while stack:remaining, path stack.pop()if not remaining:result.append(path)continuefor i in range(len(remaining)):stack.append((remaining[:i]remaining[i1:], path[remaining[i]]))return result3.2 BFS最短路径from collections import deque# BFS最短路径LeetCode 1091def shortest_path_binary_matrix(grid):n len(grid)if grid[0][0] 1 or grid[n-1][n-1] 1:return -1q 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 distfor dr, dc in dirs:nr, nc r dr, c dcif 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]*(capacity1) for _ in range(n1)]for i in range(1, n1):for j in range(1, capacity1):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]*(capacity1)for i in range(len(weights)):for j in range(weights[i], capacity1):dp[j] max(dp[j], dp[j-weights[i]] values[i])return dp[capacity]4.2 经典DP问题问题状态定义转移方程复杂度最长递增子序列dp[i] 以i结尾的LIS长度dp[i]max(dp[j]1)O(n^2)最长公共子序列dp[i][j] LCS长度相等则1O(mn)编辑距离dp[i][j] 最小操作数min(删,插,换)1O(mn)打家劫舍dp[i] 最大金额dp[i]max(dp[i-1],dp[i-2]nums[i])O(n)股票买卖dp[i][k][0/1]持有/不持有O(n)第五章 贪心算法局部最优的选择策略贪心算法在每一步选择中都采取当前最优的选择期望最终达到全局最优。虽然不总能得到最优解但在特定问题上非常高效如区间调度、跳跃游戏等。# 跳跃游戏LeetCode 55def can_jump(nums):max_reach 0for i, num in enumerate(nums):if i max_reach:return Falsemax_reach max(max_reach, i num)if max_reach len(nums) - 1:return Truereturn max_reach len(nums) - 1# 区间调度LeetCode 435def erase_overlap_intervals(intervals):if not intervals:return 0intervals.sort(keylambda x: x[1])count 0end intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] end:count 1else:end intervals[i][1]return count第六章 大厂面试高频题分布统计公司高频题型难度分布时间限制考察重点腾讯DP、图论、树Medium 70%45分钟代码规范阿里数组、字符串Easy 60%30分钟边界处理字节DP、滑动窗口Medium 80%40分钟思路清晰美团DP、BFSMedium 65%35分钟优化能力快手模拟、数学Easy 50%30分钟逻辑思维拼多多字符串、数组Easy 55%25分钟代码速度