被围绕的区域(LC130)
哪些公司问过
答案要点
- 反向思考:从边界上的 O 出发标记不会被围住的区域
- DFS 或 BFS 把与边界连通的 O 标记为临时字符
- 最后遍历:剩余 O 改为 X,临时字符还原为 O
- 原地修改,时间 O(mn)
- 大矩阵用 BFS 或显式栈防止递归栈溢出,也可用并查集
易错点
- 从内部每个 O 出发判断是否能到边界,重复搜索导致超时
- 忘记把临时标记还原为 O
- 大矩阵下递归 DFS 栈溢出
面试官常见追问
- 并查集方案怎么做?
- 岛屿数量(LC200)和这题有什么联系?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。