第4章 算法与数据结构高频题：排序、搜索、图、动态规划，手撕代码要点
本章聚焦机器人算法工程师面试中最高频的算法与数据结构手撕代码题，覆盖排序、搜索、图、动态规划四大核心模块。手撕代码是技术面的"硬通货"，直接决定面试评级。掌握一套稳定的回答框架，比刷题数量更重要。
📊 本章知识结构一览
| 模块 | 核心考点 | 面试频率 | 手撕代码要点 |
|---|---|---|---|
| 排序 | 快排 / 归并 / 堆排 | ★★★★★ | 分治思想、稳定性分析、pivot选择策略 |
| 搜索 | 二分搜索 & 旋转数组 / 二维搜索 | ★★★★★ | 区间定义、边界条件、等号处理 |
| 图 | BFS / DFS / 拓扑排序 / 最短路径 | ★★★★☆ | visited标记、遍历顺序、邻接表建图 |
| 动态规划 | 状态定义 / 转移方程 / 空间优化 | ★★★★★ | 最优子结构、状态压缩、初始化细节 |
📌 问答卡片 1 · 排序
面试问题：请实现快速排序，并分析其最好、最坏、平均时间复杂度。
| 面试官考察点 | 基础编码能力、分治思想理解、复杂度分析、pivot选择策略的工程意识 |
| 回答框架 | ① 选pivot（首尾/随机/三数取中）→ ② 分区操作（双指针交换）→ ③ 递归排序子区间 → ④ 终止条件（L≥R） |
| 简短示例回答 | 采用分治思想，选择基准元素后通过双指针一次分区，左子区小于基准，右子区大于基准，递归排序。平均 O(nlogn)，最坏 O(n²)。优化策略包括随机选择 pivot 和三路快排处理重复元素。 |
| 可能追问 | ① 如何避免最坏情况？② 三路快排与经典快排的区别？③ 快排是否稳定？如何改造为稳定排序？ |
| ⚠️ 避坑提醒 | 未明确 pivot 选择策略直接写递归；分区时忽略等号处理导致死循环；对已排序数组未做退化分析。 |
📌 问答卡片 2 · 搜索
面试问题：在旋转排序数组（如 [4,5,6,7,0,1,2]）中搜索 target，返回下标或 -1。要求时间复杂度 O(log n)。
| 面试官考察点 | 二分搜索变体能力、边界条件敏感度、旋转点定位逻辑、单调区间判断 |
| 回答框架 | ① 判空返回 -1 → ② 二分中 mid → ③ 判断左半有序还是右半有序 → ④ target 在有序区间内则缩小范围，否则进另一半 → ⑤ 循环结束返回 -1 |
| 简短示例回答 | 二分查找，先判断 mid 落在左有序区间还是右有序区间。若左有序且 target 在区间内，右指针左移；否则左指针右移。关键处理 nums[mid]==target 时直接返回，注意等号归属避免漏判。 |
| 可能追问 | ① 数组有重复元素时怎么办？② 找旋转点的最小值如何实现？③ 搜索左边界 / 右边界如何处理？ |
| ⚠️ 避坑提醒 | 未区分 "nums[mid] >= nums[left]" 的等号场景；边界判断条件写反导致死循环；忘记处理空数组输入。 |
📌 问答卡片 3 · 动态规划
面试问题：机器人从 m×n 网格左上角走到右下角，每次只能向右或向下，求不同路径总数。若有障碍物（用 1 表示）应如何处理？
| 面试官考察点 | DP 状态定义、转移方程推导、初始化细节、空间优化能力、障碍物处理的特殊情形 |
| 回答框架 | ① 定义 dp[i][j] 表示到达 (i,j) 的路径数 → ② 转移 dp[i][j]=dp[i-1][j]+dp[i][j-1]（无 obstacle 时） → ③ 初始化第一行第一列遇 obstacle 后为 0 → ④ 返回 dp[m-1][n-1] |
| 简短示例回答 | 定义 dp[i][j] 为到达 (i,j) 的路径数，无 obstacle 时 dp[i][j] = dp[i-1][j] + dp[i][j-1]，有 obstacle 时 dp[i][j] = 0。初始化第一行第一列遇障碍后全部置零。空间可优化为 O(n) 一维滚动数组。 |
| 可能追问 | ① 空间优化为 O(n) 的具体实现？② 如果要求输出所有路径怎么做？③ 路径带权重求最短路径如何转换？ |
| ⚠️ 避坑提醒 | 初始化时忽略障碍物阻断效应；dp 数组类型用 int 可能溢出；转移方程中忘记检查 obstacle 前置位；空间优化时滚动顺序写错。 |
🚀 项目案例 · 真实项目模板
本章项目案例展示 图搜索 + 动态规划 在机器人领域的典型落地场景，可迁移至路径规划、任务调度等高频面试题。
| 项目名称 | 基于 A* + JPS 的仓储机器人全局路径规划系统 |
| 业务背景 | 智能仓储中 100+ 台 AGV 需从货架区搬运货物至分拣站，要求路径无碰撞、响应快、支持动态重规划 |
| 规模指标 | 100 台 AGV 协同 · 仓库 10000㎡ · 单次规划 ≤ 50ms · 动态重规划 10Hz · 碰撞率 ＜ 0.1% |
| 技术栈 | C++17 · A* 算法 · JPS 跳点搜索 · 四叉树地图 · ROS2 Humble · Rviz 可视化 |
| 核心难点 |
|
| 面试高频追问 |
|
| 可迁移回答话术 | "在路径规划项目中，我采用 '搜索空间剪枝 + 启发式评估 + 动态重规划' 三阶段策略：首先通过 JPS |