返回文章列表

面试高频算法整理：排序、二叉树与动态规划

面试算法题是每个开发者绕不过的坎。不管是校招还是社招，面试官总喜欢扔几道算法题来考察你的思维能力和代码功底。这篇文章整理了面试中出现频率最高的几类题型，用 Dart 和 Python 双语实现，帮助你快速上手。

一、排序算法

排序是最基础的算法考点。面试中最常考的是快速排序和归并排序，要求能手写实现。

1.1 快速排序

// Dart 实现
void quickSort<T extends Comparable>(List<T> arr, int left, int right) {{
  if (left >= right) return;

  int pivotIndex = _partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);
}}

int _partition<T extends Comparable>(List<T> arr, int left, int right) {{
  T pivot = arr[right];
  int i = left;

  for (int j = left; j < right; j++) {{
    if (arr[j].compareTo(pivot) <= 0) {{
      _swap(arr, i, j);
      i++;
    }}
  }}
  _swap(arr, i, right);
  return i;
}}

void _swap<T>(List<T> arr, int i, int j) {{
  T temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}}

// Python 实现
def quick_sort(arr, left, right):
    if left >= right:
        return
    pivot_idx = partition(arr, left, right)
    quick_sort(arr, left, pivot_idx - 1)
    quick_sort(arr, pivot_idx + 1, right)

def partition(arr, left, right):
    pivot = arr[right]
    i = left
    for j in range(left, right):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[right] = arr[right], arr[i]
    return i

1.2 归并排序

// Dart 实现
List<int> mergeSort(List<int> arr) {{
  if (arr.length <= 1) return arr;

  int mid = arr.length ~/ 2;
  List<int> left = mergeSort(arr.sublist(0, mid));
  List<int> right = mergeSort(arr.sublist(mid));

  return _merge(left, right);
}}

List<int> _merge(List<int> left, List<int> right) {{
  List<int> result = [];
  int i = 0, j = 0;

  while (i < left.length && j < right.length) {{
    if (left[i] <= right[j]) {{
      result.add(left[i++]);
    }} else {{
      result.add(right[j++]);
    }}
  }}
  result.addAll(left.sublist(i));
  result.addAll(right.sublist(j));
  return result;
}}

二、二叉树遍历

二叉树是面试的"常青树"，几乎每次都有。掌握前中后序遍历和层序遍历是基本要求。

2.1 节点定义

class TreeNode {{
  int val;
  TreeNode? left;
  TreeNode? right;
  TreeNode(this.val, [this.left, this.right]);
}}

2.2 前中后序遍历（递归 + 迭代）

// 前序遍历（递归）
List<int> preorder(TreeNode? root) {{
  if (root == null) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
}}

// 中序遍历（迭代 - 用栈）
List<int> inorder(TreeNode? root) {{
  List<int> result = [];
  List<TreeNode> stack = [];
  TreeNode? current = root;

  while (current != null || stack.isNotEmpty) {{
    while (current != null) {{
      stack.add(current);
      current = current.left;
    }}
    current = stack.removeLast();
    result.add(current.val);
    current = current.right;
  }}
  return result;
}}

// 层序遍历（BFS）
List<List<int>> levelOrder(TreeNode? root) {{
  if (root == null) return [];

  List<List<int>> result = [];
  List<TreeNode> queue = [root];

  while (queue.isNotEmpty) {{
    int levelSize = queue.length;
    List<int> level = [];

    for (int i = 0; i < levelSize; i++) {{
      TreeNode node = queue.removeAt(0);
      level.add(node.val);
      if (node.left != null) queue.add(node.left!);
      if (node.right != null) queue.add(node.right!);
    }}
    result.add(level);
  }}
  return result;
}}

三、动态规划

动态规划（DP）是面试中区分度最高的题型。核心思路：找到状态定义和状态转移方程。

3.1 爬楼梯（入门）

// 每次可以爬1或2级台阶，有多少种方法？
int climbStairs(int n) {{
  if (n <= 2) return n;
  int prev1 = 2, prev2 = 1;
  for (int i = 3; i <= n; i++) {{
    int current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }}
  return prev1;
}}

3.2 0-1 背包问题

// 给定容量 W 和 n 个物品（重量 w[i]、价值 v[i]），求最大价值
int knapsack(int W, List<int> w, List<int> v) {{
  int n = w.length;
  List<List<int>> dp = List.generate(
    n + 1, (_) => List.filled(W + 1, 0),
  );

  for (int i = 1; i <= n; i++) {{
    for (int j = 1; j <= W; j++) {{
      if (w[i - 1] <= j) {{
        dp[i][j] = max(
          dp[i - 1][j],                                    // 不选
          dp[i - 1][j - w[i - 1]] + v[i - 1],           // 选
        );
      }} else {{
        dp[i][j] = dp[i - 1][j];
      }}
    }}
  }}
  return dp[n][W];
}}

3.3 最长递增子序列（LIS）

// O(n log n) 解法：二分查找 + 贪心
int lengthOfLIS(List<int> nums) {{
  List<int> tails = [];

  for (int num in nums) {{
    // 二分查找第一个 >= num 的位置
    int left = 0, right = tails.length;
    while (left < right) {{
      int mid = (left + right) ~/ 2;
      if (tails[mid] < num) {{
        left = mid + 1;
      }} else {{
        right = mid;
      }}
    }}

    if (left == tails.length) {{
      tails.add(num);
    }} else {{
      tails[left] = num;
    }}
  }}
  return tails.length;
}}

四、常用技巧总结

题型	核心思路	时间复杂度
排序	分治、双指针	O(n log n)
二叉树	递归、BFS/DFS、栈	O(n)
动态规划	状态定义 + 转移方程	O(n²) 或更优
双指针	滑动窗口、左右夹逼	O(n)
哈希表	空间换时间	O(n)

总结

算法面试的核心不是背题，而是掌握解题思路。遇到题目先想：这是什么类型？用暴力解法能不能做？能优化吗？优化空间在哪？养成这个思考习惯，比刷 1000 道题更有用。

建议每天花 30 分钟写 1-2 道算法题，坚持一个月，你会发现自己进步非常明显。