地址:https://leetcode-cn.com/problems/surface-area-of-3d-shapes/

题目

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

解题思路

一开始这个题还真是一头雾水,虽然之前做过类似的题,比如前不久才做过的“腐烂橘子”那个题,就很类似。

只要做过类似的题,应该还是很容易想到要遍历二维数组,然后对每一个元素要判断其周围的元素,如果有需要的话可能还需要动态规划、递归之类的方法来解题。

仔细思考一下,其实这个题想通了思路还挺简单的,因为并没有用到动态规划或是递归,只需要遍历一次二维数组就可以了。

首先不考虑周围格子的情况下,每一个格子上所堆叠的正方体都有一个表面积,如果没有立方体那么它的表面积为 0 ,显然也不会有与别的立方体重叠的部分;否则该单元格上堆叠的立方体的表面积应为 4 * grid[i][j] + 2

然后考虑周围格子的情况,不管周围单元格是否有立方体,与当前单元格重叠的部分始终是较少立方体的个数,也就是 grid[i][j] <= grid[ii][jj] ? grid[i][j] : grid[ii][jj] ,按照我们人的思维很容易想到应该减去2倍的重叠部分的面积,但是不能这么做,程序它不聪明,当它遍历的这个相邻单元格的时候,再一次减掉2倍的重叠部分的面积,实际上就减去了4倍的重叠部分的面积,所以我们应该只考虑当前单元格应该做的事,也就是只减掉当前单元格与相邻单元格重叠部分的面积(1倍)。

重复上述步骤遍历完整个二维数组,即可以得到最终的三维形体表面积。

代码

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int area = 0;//表面积
        vector<pair<int, int>> dir = { {-1,0},{1,0},{0,-1},{0,1} };//上、下、左、右
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 0)//没有立方体不做处理,面积不改变
                    continue;
                area += 4 * grid[i][j] + 2;//不考虑四周重叠部分的表面积
                for (auto d : dir) {
                    int ii = i + d.first;
                    int jj = j + d.second;
                    //减掉相邻立方体个数较少的一侧的面积
                    //例如4和2相邻,应减掉当前4个立方体与2相邻一侧的表面积2
                    if (ii >= 0 && ii < grid.size() && jj >= 0 && jj < grid[0].size()) {
                        area -= grid[i][j] <= grid[ii][jj] ? grid[i][j] : grid[ii][jj];
                    }
                }
            }
        }
        return area;
    }
};


Leetcode      Leetcode C++

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!