原创

每日一题-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

解决方案:

这道题最难的是读懂题意,题中输入的数组中的每一个子数组表示每列的立方体摆放形式,每个子数组中的值表示对应行的位置应列应摆放几个立方体。

知道这个意思了,题目就简单了。按照这个逻辑我们先画图看下示例二的示例图 https://static.huhuang.net/blog/9c27b08de841f9c79fb32d5dde2e175f1a79e071f1b01ec399119af40870e095-image.png

图形的表面积等于总体表面积减去覆盖的面积,也可以是每个立方体没被覆盖的面的总和。

我们先看下减法的思路: 一共由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; };

本文于   2020/3/25 下午  发布在  数学与算法  分类下,当前已被围观  129  次

相关标签: 算法与数学 每日一题

永久地址: https://huhuang.net/article/6

版权声明: 自由转载-署名-非商业性使用   |   Creative Commons BY-NC 3.0 CN