问题解决模式
解题四步法
Step 1: 理解问题
在开始编码之前，确保你完全理解问题：
- 输入是什么？ 类型、范围、约束
- 输出是什么？ 期望的格式和类型
- 有什么特殊要求？ 时间限制、空间限制
- 边界情况？ 空输入、大规模输入、重复元素
💡 提示
如果不确定，要主动提问。这展示了你的沟通能力。
Step 2: 暴力解法
先想出一个能工作的解法，即使它不是最优的：
- 明确暴力的方法是什么
- 评估其时间和空间复杂度
- 这是你的 baseline，后续会优化
Step 3: 优化
思考优化的方向：
- 空间换时间 - 使用额外的数据结构
- 时间换空间 - 预处理、预计算
- 算法改进 - 分治、动态规划、贪心
- 数据结构改进 - 用哈希表替代数组、用堆优化
Step 4: 代码实现
- 保持代码清晰和模块化
- 使用有意义的变量名
- 适当注释关键逻辑
常见问题模式
1. 两指针模式
适用于有序数组或链表问题。
python
def two_pointers(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current = arr[left] + arr[right]
if current == target:
return [left, right]
elif current < target:
left += 1
else:
right -= 1
return []典型场景：
- 两数之和（有序数组）
- 三数之和
- 验证回文串
2. 滑动窗口
适用于子数组/子串问题。
python
def sliding_window(s, k):
window = {}
left = 0
for right in range(len(s)):
# 扩展窗口
window[s[right]] = window.get(s[right], 0) + 1
# 收缩窗口
while window[s[right]] > k:
window[s[left]] -= 1
left += 1
return left典型场景：
- 最大子数组长度（限制重复元素个数）
- 字符串排列
- 最小覆盖子串
3. 二分查找变体
适用于有序数据的搜索问题。
python
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典型场景：
- 搜索旋转排序数组
- 寻找边界（第一个/最后一个位置）
- 寻找峰值元素
4. 递归与回溯
适用于组合、排列、子集问题。
python
def backtrack(result, path, choices):
if is_valid_complete(path):
result.append(path.copy())
return
for choice in choices:
if is_promising(choice):
path.append(choice)
backtrack(result, path, remaining_choices(choice))
path.pop()典型场景：
- 全排列
- 组合总和
- N 皇后问题
5. 广度优先搜索 (BFS)
适用于层次遍历、最短路径问题。
python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)典型场景：
- 二叉树层序遍历
- 图的最短路径
- 迷宫问题
6. 深度优先搜索 (DFS)
适用于遍历、连通性、路径问题。
python
def dfs(graph, node, visited):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)典型场景：
- 二叉树遍历（前/中/后序）
- 图的连通分量
- 岛屿数量问题
7. 动态规划
适用于最优子结构问题。
解题步骤：
- 确定 DP 状态（
dp[i]含义） - 推导状态转移方程
- 确定初始值
- 确定遍历顺序
python
# 一维 DP 示例：爬楼梯
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 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
prev, curr = 1, 2
for i in range(3, n + 1):
prev, curr = curr, prev + curr
return curr典型场景：
- 斐波那契数列
- 背包问题
- 最长公共子序列
8. 分治法
将问题分解为子问题，解决子问题，然后合并。
python
def divide_conquer(problem):
if is_base_case(problem):
return solve_base(problem)
sub_problems = split(problem)
sub_results = [divide_conquer(sub) for sub in sub_problems]
return merge(sub_results)典型场景：
- 归并排序
- 快速排序
- 最近点对问题
复杂度速查
| 数据结构 | 操作 | 时间复杂度 |
|---|---|---|
| 数组 | 访问、查找 | O(1)、O(n) |
| 数组 | 插入、删除 | O(n) |
| 链表 | 访问 | O(n) |
| 链表 | 头部插入/删除 | O(1) |
| 哈希表 | 查找、插入、删除 | O(1) 平均 |
| 二叉搜索树 | 查找、插入、删除 | O(log n) 平均 |
| 堆 | 查找最大/最小 | O(1) |
| 堆 | 插入、删除 | O(log n) |
| 算法 | 时间复杂度 |
|---|---|
| 冒泡/插入/选择排序 | O(n^2) |
| 归并/快速排序 | O(n log n) |
| 堆排序 | O(n log n) |
| 计数/桶排序 | O(n + k) |
| 二分查找 | O(log n) |
| 图遍历 BFS/DFS | O(V + E) |
面试技巧
- 不要急于编码 - 先思考清楚再动手
- 边想边说 - 展示你的思维过程
- 寻求确认 - "这样理解对吗？"
- 考虑边界 - 空输入、极端情况
- 多种方案 - 先说简单方案，再优化