今天要分享一道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提供面试代面,面试辅助服务,力求提高每一位候选人的面试成功率。如果您也有兴趣,欢迎联系我们。
![](https://csoahelp.com/wp-content/uploads/2024/02/image-34.png)