今天要分享一道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总是形成一个矩形或正方形吗？

面试官：是的，可以这么假设。

解题思路

初始算法

1. 检查特殊情况：首先检查网格是否为空或者网格中的行是否为空。如果是，返回周长为0。
2. 获取网格的维度：计算网格的行数和列数。
3. 定义辅助函数：定义一个辅助函数，用于检查某个位置是否超出边界。如果位置的行或列超出了网格的范围，则返回True，否则返回False。
4. 遍历网格：通过嵌套循环遍历每个单元格。
5. 检查每个单元格：
   • 如果单元格的值为1，则需要检查它的四个方向（上、下、左、右）。
   • 对于每个方向，如果相邻位置超出边界或是0，则周长加1。

面试官的反馈和修改

面试官指出了一些潜在的问题，例如需要处理建筑物内部的空地，以及确保周长计算准确。根据这些反馈，我们协助候选人对算法进行了修改。

修改后的算法

1. 初始检查和维度获取：与之前相同，首先检查网格是否为空，然后获取网格的行数和列数。
2. 定义辅助函数：检查某个位置是否超出边界。
3. 遍历网格：通过嵌套循环遍历每个单元格。
4. 识别内部空地：
   • 使用广度优先搜索（BFS）或深度优先搜索（DFS）从每个0开始遍历，检查是否能到达网格边界。
   • 如果一个0无法到达边界，则标记为内部空地。
5. 周长计算：
   • 再次遍历网格，对于每个1，检查其四个方向。如果相邻位置是0且不是内部空地，或者超出边界，则周长加1。

修改后的具体实现步骤

1. 初始化：首先，检查网格是否为空，获取网格的行数和列数。初始化一个变量用于存储周长。
2. 辅助函数：定义一个辅助函数，用于检查某个位置是否超出边界。如果某个位置的行或列小于0或大于等于行数或列数，则返回True，否则返回False。
3. 标记内部空地：
   • 遍历网格的每个位置。如果遇到0且该位置没有被访问过，启动BFS或DFS遍历。
   • 从该位置开始，如果遍历到边界，说明这是一个外部空地，否则这是一个内部空地。
   • 标记所有遍历到的内部空地。
4. 计算周长：
   • 再次遍历网格的每个位置。如果遇到1，检查其四个方向（上、下、左、右）。
   • 对于每个方向，如果相邻位置是0且不是内部空地，或者相邻位置超出边界，则周长加1。

修改后的优势

1. 考虑内部空地：新算法能够正确识别并忽略建筑物内部的空地，确保周长计算准确。
2. 处理复杂情况：能够处理多个相邻建筑物和不规则形状的建筑物，增强了算法的适用性。
3. 更全面的检查：通过BFS或DFS遍历网格，确保所有内部空地都被正确标记。

结论

通过这次面试和代码修改，候选人大大提升了在面试官面前的面试表现。我们csoahelp提供面试代面，面试辅助服务，力求提高每一位候选人的面试成功率。如果您也有兴趣，欢迎联系我们。