本题为 2025 秋招真实面试题,考察 DFS 基础 + 对结构匹配的深入理解
🎯 面试中客户拿到这题时只有模糊的思路,经过我们逐行指导,最终高质量完成!
📄 题目原文(英文)
Given a two dimensional array of bit strings representing two maps (grid1 and grid2), count the number of matching land regions.
Two cells are part of the same region if they are both land (value '1') and adjacent up/down/left/right (not diagonally).
A land region in grid2 is said to be “matching” if and only if all of its land cells are also land in grid1 and form the exact same shape.
Function Signature
int countMatchingRegions(String[] grid1, String[] grid2)
Input:
grid1[n]
: array of bit strings representing map 1grid2[n]
: array of bit strings representing map 2Output:
- An integer representing the number of matching land regions.
📘 中文翻译
给定两个大小相同的二维地图 grid1 和 grid2,它们由二进制字符串组成('1' 表示陆地,'0' 表示水域)。
每张图中,四联通(上下左右)相邻的 '1' 组成一个“陆地区域”。
你的任务是:计算 grid2 中有多少块陆地区域在 grid1 中也有且形状一致。
✅ “匹配的区域”要求:
- grid2 中的一块陆地,在 grid1 相应位置上也必须全部为陆地
- 且结构形状完全一致(不能比 grid1 少,不能多,不能错)
🧠 示例 Example
Input:
grid1 = ["111",
"100",
"100"]
grid2 = ["111",
"100",
"101"]
Output: 1
✅ 解释:
- grid2 中有两个区域,一个是左上大块 "L" 型,一个是右下角的孤点 (2,2)
- 只有左上块在 grid1 中完整匹配 → 所以返回 1
🔍 题目核心难点:
- ✅ 不是单纯计算岛屿数量,而是“两个图形之间的结构匹配判断”
- ✅ 要同步 DFS 遍历两张地图,对应位置是否都是 1
- ✅ 一旦发现不一致(比如 grid2 是 1,但 grid1 是 0),整个区域不计入
💡 我们是如何辅导客户搞定这题的?
客户初拿到题目时,只想到 “DFS 找岛”,但在面试过程中卡在“如何判断两个区域是否一致”上。我们:
- 🔧 从 DFS 的基本结构出发,手把手带客户分析两图同步遍历思路;
- 🧱 教会他用 visited 标记访问,确保每块区域只处理一次;
- 🧮 帮助客户在 DFS 过程中记录匹配状态:一旦发现一处不一致就舍弃该区域;
- ✅ 最终实现高效、简洁、逻辑清晰的完整解法,并附注释说明递归逻辑。
💬 面试官最后评价:“You handled edge cases very well and showed a solid understanding of recursive traversal.”
🎁 小结
这题其实是“岛屿数量”的衍生题,但要求更高:结构匹配 + 双图对比,在 Meta、Two Sigma、Amazon 等公司高频出现。
📮 如果你也即将迎来 Two Sigma、Amazon、TikTok、Meta 等技术面试,
不要再独自硬扛,来找我们,一起稳稳走完这场硬仗。
