本文主要是介绍883. Projection Area of 3D Shapes,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
883. 三维形体投影面积
在
N * N
的网格中,我们放置了一些与 x,y,z 三轴对齐的1 * 1 * 1
立方体。每个值
v = grid[i][j]
表示v
个正方体叠放在单元格(i, j)
上。现在,我们查看这些立方体在 xy、yz 和 zx 平面上的投影。
投影就像影子,将三维形体映射到一个二维平面上。
在这里,从顶部、前面和侧面看立方体时,我们会看到“影子”。
返回所有三个投影的总面积。
示例 1:
输入:[[2]] 输出:5
示例 2:
输入:[[1,2],[3,4]] 输出:17 解释: 这里有该形体在三个轴对齐平面上的三个投影(“阴影部分”)。
示例 3:
输入:[[1,0],[0,2]] 输出:8
示例 4:
输入:[[1,1,1],[1,0,1],[1,1,1]] 输出:14
示例 5:
输入:[[2,2,2],[2,1,2],[2,2,2]] 输出:21
提示:
1 <= grid.length = grid[0].length <= 50
0 <= grid[i][j] <= 50
解法一
//时间复杂度O(n*n), 空间复杂度O(n)
class Solution {
public:int projectionArea(vector<vector<int>>& grid) {int n = grid.size(), area = 0;vector<int> rowMax(n, 0), colMax(n, 0);for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {rowMax[i] = max(rowMax[i], grid[i][j]);colMax[j] = max(colMax[j], grid[i][j]);if(grid[i][j]) area++;}}for(int i = 0; i < n; i++) {area += (rowMax[i] + colMax[i]);}return area;}
};
解法二
class Solution {
public:int projectionArea(vector<vector<int>>& grid) {int n = grid.size(), area = 0;for(int i = 0; i < n; i++) {int rowMax = 0, colMax = 0;for(int j = 0; j < n; j++) {rowMax = max(rowMax, grid[i][j]);colMax = max(colMax, grid[j][i]);if(grid[i][j]) area++;}area += rowMax + colMax;}return area;}
};
隐含的条件: 三个方向的投影,其中xy面上投影面积是矩阵中非零元素的个数,xz和yz面上的投影面积是每一行(列)最大元素之和。
这样思路就明白了,只需要遍历矩阵,找出
- 每一行的最大元素;
- 每一列的最大元素;
- 非零元素的个数。
对这三者求和就是答案。
最低效的方法是对这三个条件遍历三次。
解法一:使用了两个额外的数组,同时记录了这三个值,最后对数组求和处理,返回结果。用时12ms。
解法二:不使用额外的空间,而是在循环体内同时进行按行遍历和按列遍历,行、列最大值保存在变量中,最后返回三者之和。用时16ms。
解法一和二各有优劣。
- 从空间上看,解法二的优点是它是O(1)的空间需求,而解法二需要O(n)的空间。
- 从时间上看,表面上看解法二没有额外的对数组的求和处理,好像解法二更加高效,但是由于解法二按列遍历,违反了空间局部性原则,导致其效率略低。这是它耗时16ms的原因之一。
提高效率的一些技巧:
- 空间局部性原则:遍历二维数组时,最好按行优先的顺序进行访问(因为行中的元素在内存中是顺序排列的);
- 循环展开:通过增加每次迭带计算的元素的数量,减少迭代次数。例如对一维数组从1到n求和,常规做法是在循环体内对变量sum += a[i];而利用循环展开的做法是,使用两个变量sum1 = a[i], sum2 = a[i + 1],i可以一次加2,最后对sum1和sum2求和。
- 尽量减少内存引用。
- 避免不必要的重复计算:这个例子很常见,对于如下代码,后者会更高效一些。
//形式1:for(int i = 0; i < vec.size(); i++) {...}//形式2:更好的改进int len = vec.size();for(int i = 0; i < len; i++) {...}
这部分知识要以参考《深入理解计算机系统》(CSAPP)的第5章和第6章。
这篇关于883. Projection Area of 3D Shapes的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!