leetcode:那些年我遇到过的编程题011:三维型体的表面积
程序员文章站
2022-06-10 19:17:37
...
leetcode:那些年我遇到过的编程题011:三维型体的表面积
在 N * N 的网格上,我们放置一些 1 * 1 * 1 的立方体。
每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
请你返回最终形体的表面积。
示例 1:
输入:[[2]]
输出:10
示例 2:
输入:[[1,2],[3,4]]
输出:34
示例 3:
输入:[[1,0],[0,2]]
输出:16
示例 4:
输入:[[1,1,1],[1,0,1],[1,1,1]]
输出:32
示例 5:
输入:[[2,2,2],[2,1,2],[2,2,2]]
输出:46
提示:
1 <= N <= 50
0 <= grid[i][j] <= 50
我想到了一种方法,这个组合型体的表面积等于它的三视图的面积乘以2.所以我们只要计算出这个型体三视图的面积就好。但是,又看了后边几个例子我发现这个方法并不对,这个方法要求了型体本身不能出现凹进去的形状,所以这个方法pass。
我又想了想,能不能把这个型体的三维数据构造出来,有正方体的位置值就为1,因为每个正方体如果周围没有别的正方体的话,它的表面积正常为6,每在它周围出现一个正方体,表面积就会减1,对每一个存在正方体检测它的六个面,最后求和。
class Solution {
public int surfaceArea(int[][] grid) {
//因为后边三维数组创建是从(1,1,1)开始的,所以要增大容量。
int[][][] xYZ = new int[52][52][52];
int res = 0;
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[0].length;j++){
if(grid[i][j]>0){
for(int h = 1;h<= grid[i][j];h++){
xYZ[i+1][j+1][h] = 1;
}
}
}
}
for(int i=1; i <51;i++){
for(int j=1; j<51;j++){
for(int k=1; k <51;k++){
if(xYZ[i][j][k] == 1){
res+=Test(i,j,k,xYZ);
}
}
}
}
return res;
}
public int Test(int x,int y,int z,int xYZ[][][]){
int area = 6;
if(xYZ[x-1][y][z] == 1) area--;
if(xYZ[x][y-1][z] == 1) area--;
if(xYZ[x][y][z-1] == 1) area--;
if(xYZ[x+1][y][z] == 1) area--;
if(xYZ[x][y+1][z] == 1) area--;
if(xYZ[x][y][z+1] == 1) area--;
return area;
}
}
官方答案:是利用所有贴合的面会导致表面积-2来计算的,把这个数组从左到右开始遍历,只需要计算每一个正方形面积内的正方体与和它上边左边相邻的正方形面积内的正方体重合的表面,最后就能计算出整个型体所重合的正方体表面。
class Solution {
public int surfaceArea(int[][] grid) {
int n = grid.length;
int res = 0;
for(int i = 0 ; i < n ;i++){
for(int j = 0 ; j < n ;j++){
int level = grid[i][j];
if(level>0){
res+=(level<<2)+2;
res-=i>0?Math.min(grid[i-1][j],level)<<1:0;
res-=j>0?Math.min(grid[i][j-1],level)<<1:0;
}
}
}
return res;
}
}