2020-03-25 三维形体的表面积

在 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

来源:力扣(LeetCode)

C++1

解题思路:
此题题意不容易理解,但是观察示例可以辅助理解题意:
首先立方体的任意一个面的面积为1。给定一个二维数组grid,每个元素代表该位置上的正方体数量,每两个相邻的正方体之间会有面的重叠,是不计入表面积的,但是最底层的正方体的下表面是表面积的一部分,求最后摆出的整体形体的表面积。

主要的难点就是如何计算某个正方体和上下左右的正方体的重叠面积,将其减掉,注意不要重复计算。

解决办法:从左上角遍历二维数组,每个位置堆叠的正方体的个数乘以4代表4个侧面的表面积总数,再加上最上面和最底层的面的面积2即可算出当前位置的总表面积res,在分别和左边和上边的位置堆叠的立方体做高度的比较,分别取最小高度h1,h2,则它们分别乘以2就是每个方向需要减去的表面积的数量,最后累计求出表面积的和即可。

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int s = grid.size(),res=0;
        for(int i=0;i<s;i++){
            for(int j=0;j<s;j++){
                int value = grid[i][j];
                if(value>0){
                    res+=value*4+2;
                    if(i>0)
                        res-=min(value, grid[i-1][j])*2;
                    if(j>0)
                        res-=min(value, grid[i][j-1])*2;
                }
            }
        }
        return res;
    }
};

C++2

思路:
单独计算每一个 v = grid[i][j] 所贡献的表面积,再将所有的 v 值相加就能得到最终形体的表面积:

对于顶面和底面的表面积,如果 v > 0,那么顶面和底面各贡献了 1 的表面积,总计 2 的表面积;

对于四个侧面的表面积,只有在相邻位置的高度小于 v 时,对应的那个侧面才会贡献表面积,且贡献的数量为 v - nv,其中 nv 是相邻位置的高度。我们可以将其写成 max(v - nv, 0)。

举一个例子,对于网格

1 5
6 7

而言,位置 grid[0][1] 的高度为 5:

因为 5 > 0,所以贡献了 2 的顶面和底面表面积;

该位置的上方和右侧没有单元格,可以看成高度为 0,所以分别贡献了 max(5 - 0, 0) = 5 的表面积;

该位置的左侧高度为 1,所以贡献了 max(5 - 1, 0) = 4 的表面积;

该位置的下方高度为 7,所以贡献了 max(5 - 7, 0) = 0 的表面积。

因此 grid[0][1] 贡献的表面积总和为 2 + 5 + 5 + 4 + 0 = 16。

算法

对于每个 v = grid[r][c] > 0,计算 ans += 2,对于 grid[r][c] 四个方向的每个相邻值 nv 还要加上 max(v - nv, 0)。

来源:LeetCode-Solution

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int dr[]{0, 1, 0, -1};
        int dc[]{1, 0, -1, 0};

        int N = grid.size();
        int ans = 0;

        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                if (grid[r][c] > 0) {
                    ans += 2;
                    for (int k = 0; k < 4; ++k) {
                        int nr = r + dr[k];
                        int nc = c + dc[k];
                        int nv = 0;
                        if (0 <= nr && nr < N && 0 <= nc && nc < N)
                            nv = grid[nr][nc];

                        ans += max(grid[r][c] - nv, 0);
                    }
                }

        return ans;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,033评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,725评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,473评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,846评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,848评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,691评论 1 282
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,053评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,700评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,856评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,676评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,787评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,430评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,034评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,990评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,218评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,174评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,526评论 2 343

推荐阅读更多精彩内容