每日一题-892.三维形体的表面积
在 N * N 的网格上,我们放置一些 1 * 1 * 1 的立方体。
每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
请你返回最终形体的表面积。
示例 1:
- 1
- 2
输入:[[2]]
输出:10
示例 2:
- 1
- 2
输入:[[1,2],[3,4]]
输出:34
示例 3:
- 1
- 2
输入:[[1,0],[0,2]]
输出:16
示例 4:
- 1
- 2
输入:[[1,1,1],[1,0,1],[1,1,1]]
输出:32
示例 5:
- 1
- 2
输入:[[2,2,2],[2,1,2],[2,2,2]]
输出:46
提示:
- 1
- 2
1 <= N <= 50
0 <= grid[i][j] <= 50
解决方案:
这道题最难的是读懂题意,题中输入的数组中的每一个子数组表示每列的立方体摆放形式,每个子数组中的值表示对应行的位置应列应摆放几个立方体。
知道这个意思了,题目就简单了。按照这个逻辑我们先画图看下示例二的示例图
图形的表面积等于总体表面积减去覆盖的面积,也可以是每个立方体没被覆盖的面的总和。
我们先看下减法的思路: 一共由1+2+3+4个立方体,共10个。每个立方体面积为1*6也就是6,总面积为60。每个图形的实际覆盖面于它相邻的方块有关,每相邻一个少一个。整体图形可以看作多个柱形组成的图形,高度为h的柱形内部相邻为h-1,与高度为h1相邻柱形的覆盖面为min(h,h1)。由于这两个柱形的相邻覆盖面积是相等的,所以可以合为2*min(h,h1)。计算下来为26.由此可以得出我们想要的答案34
具体代码过程:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
/**
* @param {number[][]} grid
* @return {number}
*/
var surfaceArea = function (grid) {
// 立方体的个数
var count = 0;
// 总覆盖面
var cover = 0;
var length = grid.length;
for (var index = 0; index < length; index++) {
for (var i = 0; i < grid[index].length; i++) {
count += grid[index][i];
if (grid[index][i] > 0) {
// 叠起来的 v 个立方体有 v-1 个接触面
cover += grid[index][i] - 1;
}
if (index > 0) {
// 当前柱子与左边柱子的接触面数量
cover += Math.min(grid[index - 1][i], grid[index][i]);
}
if (i > 0) {
// 当前柱子与上边柱子的接触面数量
cover += Math.min(grid[index][i - 1], grid[index][i]);
}
}
}
return 6 * count - 2 * cover;
};
再看下加法的思路: 我们可以将单元格 (i, j) 上堆叠的 v 个正方体看成一个高度为 v 的柱子,然后分别计算每个柱子的表面积。
首先,v > 0 的话,柱子顶部、底部的表面积都是 1。
然后是上、下、左、右四个侧面的表面积。以左侧的表面积为例:
如果柱子位于网格左边缘,左侧没有其他柱子,那么左侧表面积为 v; 如果柱子比左边的柱子矮,那么左侧露不出来,表面积为 0; 如果柱子比左边的柱子高,假设左边柱子高度为 v',那么左边露出来的表面积为 v - v'。 我们可以把三种情况合并成一个表达式:j-1 >= 0 ? Math.max(grid[i][j] - grid[i][j-1], 0) : grid[i][j]。
其余的三个侧面以此类推。这样写出题解代码:
具体代码过程:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
/**
* @param {number[][]} grid
* @return {number}
*/
var surfaceArea = function (grid) {
var total = 0;
var length = grid.length;
for (var index = 0; index < length; index++) {
for (var i = 0; i < grid[index].length; i++) {
// 左边边露出的表面积
total += index - 1 >= 0 ? Math.max(grid[index][i] - grid[index - 1][i], 0) : grid[index][i];
// 右边露出的表面积
total += index + 1 < length ? Math.max(grid[index][i] - grid[index + 1][i], 0) : grid[index][i];
// 上边露出的表面积
total += i - 1 >= 0 ? Math.max(grid[index][i] - grid[index][i - 1], 0) : grid[index][i];
//下边露出的表面积
total += i + 1 < length ? Math.max(grid[index][i] - grid[index][i + 1], 0) : grid[index][i];
// 顶部、底部的表面积
total += 2 * (grid[index][i] > 0 ? 1 : 0);
}
}
return total;
};