今天要分享一道snap的面试真题，这道题要求我们计算建筑物的周长。这是一个关于网格的题目，每个位置代表一个1米×1米的土地。网格中的数字0表示该位置没有建筑物，数字1表示该位置有建筑物。假设网格中至多有一个建筑物，题目要求返回该建筑物的周长。
题目描述
我们有一个R行C列的整数数组，表示建筑工地的俯视图。数组中的每个位置代表一个1米×1米的土地。在这个数组中，0表示该位置没有建筑物，1表示该位置有建筑物。
假设该工地上最多只能规划一栋建筑物。计算并返回该建筑物的周长。
You're given an R-by-C array of integers that represents a top-down map of abuilding construction site, where each location in the array represents a one-meter byone-meter square of land. In this array, a 0 means that there will be nothing built onthat square, and a l means that the building will include that square.
Assume that at most one building is planned for the site. Return the perimeter of
that building.
示例
示例 1
输入:
[[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 0]]
输出: 4
示例 2
输入:
[[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0]]
输出: 8
在面试过程中，候选人与面试官进行了如下对话：
候选人：我们可以假设这些1总是形成一个矩形或正方形吗？
面试官：是的，可以这么假设。
解题思路
初始算法
- 检查特殊情况：首先检查网格是否为空或者网格中的行是否为空。如果是，返回周长为0。
- 获取网格的维度：计算网格的行数和列数。
- 定义辅助函数：定义一个辅助函数，用于检查某个位置是否超出边界。如果位置的行或列超出了网格的范围，则返回True，否则返回False。
- 遍历网格：通过嵌套循环遍历每个单元格。
- 检查每个单元格：
- 如果单元格的值为1，则需要检查它的四个方向（上、下、左、右）。
- 对于每个方向，如果相邻位置超出边界或是0，则周长加1。
面试官的反馈和修改
面试官指出了一些潜在的问题，例如需要处理建筑物内部的空地，以及确保周长计算准确。根据这些反馈，我们协助候选人对算法进行了修改。
修改后的算法
- 初始检查和维度获取：与之前相同，首先检查网格是否为空，然后获取网格的行数和列数。
- 定义辅助函数：检查某个位置是否超出边界。
- 遍历网格：通过嵌套循环遍历每个单元格。
- 识别内部空地：
- 使用广度优先搜索（BFS）或深度优先搜索（DFS）从每个0开始遍历，检查是否能到达网格边界。
- 如果一个0无法到达边界，则标记为内部空地。
- 周长计算：
- 再次遍历网格，对于每个1，检查其四个方向。如果相邻位置是0且不是内部空地，或者超出边界，则周长加1。
修改后的具体实现步骤
- 初始化：首先，检查网格是否为空，获取网格的行数和列数。初始化一个变量用于存储周长。
- 辅助函数：定义一个辅助函数，用于检查某个位置是否超出边界。如果某个位置的行或列小于0或大于等于行数或列数，则返回True，否则返回False。
- 标记内部空地：
- 遍历网格的每个位置。如果遇到0且该位置没有被访问过，启动BFS或DFS遍历。
- 从该位置开始，如果遍历到边界，说明这是一个外部空地，否则这是一个内部空地。
- 标记所有遍历到的内部空地。
- 计算周长：
- 再次遍历网格的每个位置。如果遇到1，检查其四个方向（上、下、左、右）。
- 对于每个方向，如果相邻位置是0且不是内部空地，或者相邻位置超出边界，则周长加1。
修改后的优势
- 考虑内部空地：新算法能够正确识别并忽略建筑物内部的空地，确保周长计算准确。
- 处理复杂情况：能够处理多个相邻建筑物和不规则形状的建筑物，增强了算法的适用性。
- 更全面的检查：通过BFS或DFS遍历网格，确保所有内部空地都被正确标记。
结论
通过这次面试和代码修改，候选人大大提升了在面试官面前的面试表现。我们csoahelp提供面试代面，面试辅助服务，力求提高每一位候选人的面试成功率。如果您也有兴趣，欢迎联系我们。
