引言：为什么需要编程题库精选实战指南？
在当今快速发展的科技行业，编程面试已成为评估开发者技能的核心标准。无论是初级工程师还是资深专家，面对算法和数据结构的挑战时，往往需要系统化的准备。信息编程题库精选实战指南正是为此而生——它不仅仅是一本题库，更是一套从基础到高阶的完整学习路径，帮助你构建坚实的算法基础，掌握高效解题技巧，并在面试中脱颖而出。
根据LeetCode、HackerRank等平台的统计，超过80%的技术面试包含算法题目，而系统准备的候选人通过率提升3倍以上。本指南将覆盖：
- 基础篇：数组、字符串、链表等核心数据结构
- 进阶篇：树、图、堆等复杂结构
- 高阶篇：动态规划、回溯、贪心等高级算法
- 实战篇：面试真题解析与优化技巧
通过本指南，你将获得：
- 清晰的知识体系框架
- 详细的代码实现与注释
- 时间/空间复杂度分析
- 面试常见陷阱与规避策略
第一部分：基础数据结构与算法（面试必考）
1.1 数组与字符串操作
数组是最基础的数据结构，但面试中常考察其边界处理和优化技巧。
经典问题：两数之和（Two Sum）
def two_sum(nums, target):
"""
给定一个整数数组和目标值，找出两个数使它们的和为目标值。
时间复杂度：O(n)，空间复杂度：O(n)
"""
hash_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_map:
return [hash_map[complement], i]
hash_map[num] = i
return []
# 测试用例
print(two_sum([2, 7, 11, 15], 9)) # 输出: [0, 1]
print(two_sum([3, 2, 4], 6)) # 输出: [1, 2]
关键点解析：
- 使用哈希表将查找时间从O(n)降到O(1)
- 注意处理重复元素的情况
- 边界条件：数组长度小于2时应返回空
字符串操作：有效的字母异位词
def is_anagram(s, t):
"""
判断两个字符串是否为字母异位词（字符相同但顺序不同）
"""
if len(s) != len(t):
return False
count = {}
for char in s:
count[char] = count.get(char, 0) + 1
for char in t:
if char not in count or count[char] == 0:
return False
count[char] -= 1
return True
# 优化版本：使用固定大小数组（假设仅小写字母）
def is_anagram_optimized(s, t):
if len(s) != len(t):
return False
char_count = [0] * 26
for i in range(len(s)):
char_count[ord(s[i]) - ord('a')] += 1
char_count[ord(t[i]) - ord('a')] -= 1
return all(count == 0 for count in char_count)
1.2 链表操作
链表是面试高频考点，重点考察指针操作和边界处理。
单链表反转
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
"""
迭代法反转链表
时间复杂度：O(n)，空间复杂度：O(1)
"""
prev = None
current = head
while current:
next_node = current.next # 临时保存下一个节点
current.next = prev # 反转指针
prev = current # 移动prev
current = next_node # 移动current
return prev
# 递归法反转链表
def reverse_list_recursive(head):
if not head or not head.next:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head
head.next = None
return new_head
# 测试代码
def print_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
# 构建链表 1->2->3->4->5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
reversed_head = reverse_list(head)
print(print_list(reversed_head)) # 输出: [5, 4, 3, 2, 1]
链表环检测
def has_cycle(head):
"""
快慢指针法检测链表是否有环
时间复杂度：O(n)，空间复杂度：O(1)
"""
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
1.3 栈与队列
有效括号匹配
def is_valid_parentheses(s):
"""
判断字符串中的括号是否有效匹配
时间复杂度：O(n)，空间复杂度：O(n)
"""
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping.values():
stack.append(char)
elif char in mapping:
if not stack or stack.pop() != mapping[char]:
return False
else:
continue # 忽略非括号字符
return not stack
# 测试用例
print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("(]")) # False
print(is_valid_parentheses("([)]")) # False
用队列实现栈
from collections import deque
class MyStack:
"""
使用两个队列实现栈的push、pop、top操作
"""
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
def push(self, x):
self.queue1.append(x)
def pop(self):
while len(self.queue1) > 1:
self.queue2.append(self.queue1.popleft())
pop_element = self.queue1.popleft()
# 交换队列
self.queue1, self.queue2 = self.queue2, self.queue1
return pop_element
def top(self):
while len(self.queue1) > 1:
self.queue2.append(self.queue1.popleft())
top_element = self.queue1[0]
# 将元素移到queue2并交换
self.queue2.append(self.queue1.popleft())
self.queue1, self.queue2 = self.queue2, self.queue1
return top_element
def empty(self):
return len(self.queue1) == 0
第二部分：进阶数据结构（树与图）
2.1 二叉树遍历
前序、中序、后序遍历的递归与非递归实现
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 递归前序遍历
def preorder_traversal(root):
result = []
def dfs(node):
if not node:
return
result.append(node.val) # 根
dfs(node.left) # 左
dfs(node.right) # 右
dfs(root)
return result
# 非递归前序遍历（使用栈）
def preorder_traversal_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# 先右后左，保证左子树先访问
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
# 中序遍历（非递归）
def inorder_traversal_iterative(root):
result = []
stack = []
current = root
while current or stack:
# 一直向左走到底
while current:
stack.append(current)
current = current.left
# 访问节点
current = stack.pop()
result.append(current.val)
# 转向右子树
current = current.right
return result
# 后序遍历（非递归，双栈法）
def postorder_traversal_iterative(root):
if not root:
return []
stack1 = [root]
stack2 = []
while stack1:
node = stack1.pop()
stack2.append(node.val)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
return stack2[::-1]
层序遍历（BFS）
from collections import deque
def level_order_traversal(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
2.2 二叉搜索树（BST）
验证二叉搜索树
def is_valid_bst(root):
"""
中序遍历应为递增序列
"""
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
traversal = inorder(root)
for i in range(1, len(traversal)):
if traversal[i] <= traversal[i-1]:
return False
return True
# 优化版本：使用递归上下界
def is_valid_bst_optimized(root, min_val=float('-inf'), max_val=float('inf')):
if not root:
return True
if root.val <= min_val or root.val >= max_val:
return False
return (is_valid_bst_optimized(root.left, min_val, root.val) and
is_valid_bst_optimized(root.right, root.val, max_val))
二叉搜索树中第K小的元素
def kth_smallest(root, k):
"""
利用BST的中序遍历特性
"""
stack = []
current = root
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
k -= 1
if k == 0:
return current.val
current = current.right
return -1
2.3 图论基础
图的表示方法
# 邻接表表示（推荐）
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 邻接矩阵表示（适合稠密图）
# 0表示无边，1表示有边
adj_matrix = [
[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 0]
]
深度优先搜索（DFS）
def dfs_graph(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs_graph(graph, neighbor, visited)
# 使用DFS检测图的连通分量
def count_connected_components(graph):
visited = set()
count = 0
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for node in graph:
if node not in visited:
dfs(node)
count += 1
return count
广度优先搜索（BFS）
from collections import deque
def bfs_graph(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# BFS求最短路径（无权图）
def shortest_path(graph, start, end):
if start == end:
return [start]
queue = deque([(start, [start])])
visited = set([start])
while queue:
node, path = queue.popleft()
for neighbor in graph[node]:
if neighbor == end:
return path + [neighbor]
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # 无路径
第三部分：高阶算法（面试杀手锏）
3.1 动态规划（Dynamic Programming）
动态规划是面试中最难但也是最能体现实力的部分。
爬楼梯问题（基础DP）
def climb_stairs(n):
"""
每次可以爬1或2步，问有多少种方法爬到顶部
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
"""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 空间优化版本（只保留前两个状态）
def climb_stairs_optimized(n):
if n <= 2:
return n
prev2 = 1 # dp[i-2]
prev1 = 2 # dp[i-1]
for i in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
零钱兑换（Coin Change）
def coin_change(coins, amount):
"""
求组成金额amount所需的最少硬币数
状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)
"""
# 初始化为amount+1（表示不可达）
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != amount + 1 else -1
# 测试
print(coin_change([1, 2, 5], 11)) # 输出: 3 (5+5+1)
print(coin_change([2], 3)) # 输出: -1
最长递增子序列（LIS）
def length_of_lis(nums):
"""
时间复杂度：O(n²)
状态：dp[i]表示以nums[i]结尾的最长递增子序列长度
"""
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 优化版本：二分查找 O(n log n)
def length_of_lis_optimized(nums):
import bisect
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
背包问题（0/1背包）
def knapsack(weights, values, capacity):
"""
0/1背包问题：每个物品只能选或不选
dp[i][j]表示前i个物品在容量j下的最大价值
"""
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] = max(
dp[i-1][j], # 不选
dp[i-1][j - weights[i-1]] + values[i-1] # 选
)
else:
dp[i][j] = dp[i-1][j]
return dp[n][capacity]
# 空间优化版本（一维数组）
def knapsack_optimized(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
# 必须逆序遍历，避免重复选择
for j in range(capacity, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
# 测试
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity)) # 输出: 9
3.2 回溯算法（Backtracking）
回溯是解决排列、组合、子集问题的通用框架。
全排列（Permutations）
def permute(nums):
"""
生成所有可能的排列
时间复杂度：O(n!)
"""
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i in range(len(remaining)):
# 选择当前元素
path.append(remaining[i])
# 递归处理剩余元素
backtrack(path, remaining[:i] + remaining[i+1:])
# 撤销选择（回溯）
path.pop()
result = []
backtrack([], nums)
return result
# 优化版本：使用used数组避免复制列表
def permute_optimized(nums):
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if not used[i]:
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
result = []
used = [False] * len(nums)
backtrack([])
return result
print(permute([1, 2, 3]))
# 输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
组合问题（Combinations）
def combine(n, k):
"""
从1..n中选择k个数字的所有组合
"""
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
# 剪枝：剩余数字不够时提前终止
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
result = []
backtrack(1, [])
return result
print(combine(4, 2))
# 输出: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
子集（Subsets）
def subsets(nums):
"""
生成所有可能的子集
"""
def backtrack(start, path):
result.append(path[:]) # 每个路径都是一个子集
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
result = []
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# 输出: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
N皇后问题
def solve_n_queens(n):
"""
在n×n棋盘上放置n个皇后，使其互不攻击
"""
def backtrack(row):
if row == n:
result.append([''.join(board) for board in board_copy])
return
for col in range(n):
if is_safe(row, col):
board[row][col] = 'Q'
board_copy[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
board_copy[row][col] = '.'
def is_safe(row, col):
# 检查列冲突
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上对角线
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 检查右上对角线
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
result = []
board = [['.'] * n for _ in range(n)]
board_copy = [['.'] * n for _ in range(n)]
backtrack(0)
return result
print(solve_n_queens(4))
# 输出: [ ['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..'] ]
3.3 贪心算法（Greedy）
贪心算法在特定问题上非常高效，但需要证明其正确性。
跳跃游戏（Jump Game）
def can_jump(nums):
"""
判断是否能从数组第一个位置跳到最后一个位置
贪心策略：维护当前能到达的最远位置
"""
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1:
return True
return False
print(can_jump([2,3,1,1,4])) # True
print(can_jump([3,2,1,0,4])) # False
最小覆盖子串（Minimum Window Substring）
from collections import Counter
def min_window(s, t):
"""
在s中找到包含t所有字符的最短子串
滑动窗口 + 贪心
"""
if not s or not t or len(s) < len(t):
return ""
t_count = Counter(t)
required = len(t_count)
left, right = 0, 0
formed = 0
window_counts = {}
# 记录最短子串的长度和起始位置
min_len = float('inf')
result_left = 0
while right < len(s):
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
if char in t_count and window_counts[char] == t_count[char]:
formed += 1
# 尝试收缩窗口
while left <= right and formed == required:
char = s[left]
# 更新结果
if right - left + 1 < min_len:
min_len = right - left + 1
result_left = left
window_counts[char] -= 1
if char in t_count and window_counts[char] < t_count[char]:
formed -= 1
left += 1
right += 1
return "" if min_len == float('inf') else s[result_left:result_left + min_len]
print(min_window("ADOBECODEBANC", "ABC")) # 输出: "BANC"
第四部分：高级主题与优化技巧
4.1 位运算与数学技巧
位运算基础
# 判断是否是2的幂
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
# 计算汉明权重（1的个数）
def hamming_weight(n):
count = 0
while n:
n &= n - 1 # 清除最低位的1
count += 1
return count
# 只出现一次的数字（其他数字出现两次）
def single_number(nums):
result = 0
for num in nums:
result ^= num
return result
快速幂算法
def my_pow(x, n):
"""
计算x的n次幂，时间复杂度O(log n)
"""
if n == 0:
return 1
if n < 0:
x = 1 / x
n = -n
result = 1
current = x
while n > 0:
if n % 2 == 1:
result *= current
current *= current
n //= 2
return result
print(my_pow(2, 10)) # 1024
print(my_pow(2.0, -2)) # 0.25
4.2 并查集（Union-Find）
并查集是处理动态连通性问题的利器。
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
# 路径压缩
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
# 按秩合并
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
# 使用示例：岛屿数量
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
uf = UnionFind(rows * cols + 1) # 额外一个虚拟节点
# 将所有水域连接到虚拟节点
water = rows * cols
for i in range(rows):
for j in range(cols):
if grid[i][j] == '0':
uf.union(i * cols + j, water)
else:
# 连接相邻的陆地
if i > 0 and grid[i-1][j] == '1':
uf.union(i * cols + j, (i-1) * cols + j)
if j > 0 and grid[i][j-1] == '1':
uf.union(i * cols + j, i * cols + j - 1)
# 统计独立的陆地数量
islands = set()
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
islands.add(uf.find(i * cols + j))
return len(islands)
4.3 滑动窗口技术
最小覆盖子串（已展示） 长度为K的子数组的最大值
from collections import deque
def max_sliding_window(nums, k):
"""
使用双端队列维护窗口内的最大值
时间复杂度：O(n)
"""
if not nums:
return []
result = []
dq = deque() # 存储索引，保持递减顺序
for i in range(len(nums)):
# 移除超出窗口的元素
if dq and dq[0] == i - k:
dq.popleft()
# 移除队列中比当前元素小的元素
while dq and nums[dq[-1]] < nums[i]:
dq.pop()
dq.append(i)
# 当窗口形成后，记录最大值
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# 输出: [3,3,5,5,6,7]
第五部分：面试实战技巧与真题解析
5.1 面试准备策略
1. 理解题目要求（5分钟）
- 大声读题，确认理解无误
- 询问输入输出格式、数据范围
- 确认边界条件
2. 设计解决方案（10分钟）
- 先说暴力解法，分析时间复杂度
- 思考优化方向（空间换时间、预处理、数据结构）
- 画图辅助理解（树、图、状态转移）
3. 编写代码（15分钟）
- 先写框架，再填细节
- 边写边解释思路
- 处理边界情况
4. 测试与优化（5分钟）
- 用典型用例测试
- 分析复杂度
- 讨论可能的改进
5.2 高频面试真题
真题1：LRU缓存机制（设计题）
class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cache = {}
self.capacity = capacity
self.size = 0
self.head = DLinkedNode() # 虚拟头节点
self.tail = DLinkedNode() # 虚拟尾节点
self.head.next = self.tail
self.tail.prev = self.head
def _add_to_head(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _move_to_head(self, node):
self._remove_node(node)
self._add_to_head(node)
def _pop_tail(self):
res = self.tail.prev
self._remove_node(res)
return res
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._move_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
if key not in self.cache:
new_node = DLinkedNode(key, value)
self.cache[key] = new_node
self._add_to_head(new_node)
self.size += 1
if self.size > self.capacity:
removed = self._pop_tail()
self.cache.pop(removed.key)
self.size -= 1
else:
node = self.cache[key]
node.value = value
self._move_to_head(node)
# 测试
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print(lru.get(1)) # 1
lru.put(3, 3) # 淘汰2
print(lru.get(2)) # -1
真题2：接雨水（Trapping Rain Water）
def trap(height):
"""
双指针法：O(n)时间，O(1)空间
"""
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 输出: 6
真题3：合并K个升序链表
import heapq
def merge_k_lists(lists):
"""
使用最小堆合并K个升序链表
时间复杂度：O(N log k)，N是总节点数
"""
if not lists:
return None
# 创建虚拟头节点
dummy = ListNode(0)
current = dummy
# 初始化堆
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
while heap:
val, idx, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, idx, node.next))
return dummy.next
真题4：寻找两个正序数组的中位数
def find_median_sorted_arrays(nums1, nums2):
"""
二分查找法：O(log(min(m,n)))
"""
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total = m + n
half = total // 2
left, right = 0, m - 1
while True:
i = (left + right) // 2 # nums1的分割点
j = half - i - 2 # nums2的分割点
nums1_left = nums1[i] if i >= 0 else float('-inf')
nums1_right = nums1[i + 1] if i + 1 < m else float('inf')
nums2_left = nums2[j] if j >= 0 else float('-inf')
nums2_right = nums2[j + 1] if j + 1 < n else float('inf')
if nums1_left <= nums2_right and nums2_left <= nums1_right:
if total % 2 == 1:
return min(nums1_right, nums2_right)
return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 2
elif nums1_left > nums2_right:
right = i - 1
else:
left = i + 1
print(find_median_sorted_arrays([1, 3], [2])) # 2.0
print(find_median_sorted_arrays([1, 2], [3, 4])) # 2.5
5.3 面试常见陷阱与规避策略
陷阱1：忽略边界条件
# 错误示例：未处理空输入
def bad_example(nums):
return nums[0] # 空数组会崩溃
# 正确示例：防御性编程
def good_example(nums):
if not nums:
return None # 或抛出异常
return nums[0]
陷阱2：整数溢出
# 错误：计算阶乘时溢出
def factorial(n):
result = 1
for i in range(1, n+1):
result *= i # n>20时溢出
return result
# 正确：使用模运算或大数处理
def factorial_mod(n, mod=10**9+7):
result = 1
for i in range(1, n+1):
result = (result * i) % mod
return result
陷阱3：未考虑负数情况
# 错误：二分查找边界
def binary_search_bad(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 正确：处理重复元素和边界
def binary_search_good(arr, target):
left, right = 0, len(arr) - 1
# 寻找左边界
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left if arr[left] == target else -1
第六部分：学习路径与资源推荐
6.1 3个月学习计划
第1个月：基础夯实
- 周1-2：数组、字符串、链表（每天3题）
- 周3-4：栈、队列、哈希表（每天3题）
- 周5-6：二叉树基础遍历（每天3题）
第2个月：进阶提升
- 周1-2：二叉搜索树、图论（每天4题）
- 周3-4：动态规划基础（每天4题）
- 周5-6：回溯算法（每天4题）
第3个月：高阶冲刺
- 周1-2：高级DP、贪心（每天5题）
- 儿3-4：位运算、数学技巧（每天5题）
- 周5-6：真题模拟、面试技巧（每天2套完整面试题）
6.2 推荐资源
在线平台
- LeetCode：https://leetcode.com（最全面的题库）
- 牛客网：https://www.nowcoder.com（国内面试真题）
- LintCode：https://www.lintcode.com（阶梯式训练）
书籍推荐
- 《算法导论》：理论基础
- 《剑指Offer》：面试经典
- 《编程珠玑》：思维训练
视频课程
- Coursera算法专项课程
- 牛客网面试真题解析
- B站算法讲解视频
6.3 面试前一周 checklist
- [ ] 复习所有错题本
- [ ] 模拟3-5次完整面试
- [ ] 准备自我介绍和项目介绍
- [ ] 熟悉目标公司的技术栈
- [ ] 调整作息，保证面试状态
结语：从理论到实践的飞跃
编程面试不仅是知识的考察，更是解决问题能力的检验。本指南提供了从基础到高阶的完整学习路径，但真正的掌握需要你：
- 动手实践：每个例子都要自己敲一遍
- 总结归纳：建立自己的知识体系
- 持续练习：保持手感，每天至少1题
- 交流讨论：加入学习小组，互相讲解
记住，算法学习没有捷径，但有方法。按照本指南的路径坚持3个月，你一定能轻松应对面试挑战，实现技能的全面提升！
最后送给大家一句话：算法不是背诵，而是理解；面试不是考试，而是交流。祝你面试顺利，拿到心仪的Offer！