首页 > 其他 > 详细

Leetcode daily 20/03/26 三维形体的表面积

时间:2020-03-26 12:29:45      阅读:38      评论:0      收藏:0      [点我收藏+]

三维形体的表面积

-题目-

在?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-

??一个1 * 1 * 1的立方体表面积是6。当几个立方体叠放起来,会有一些面被“盖住”,产生表面积的损失。若叠放数量为elem,则网格某个位置的叠放立方体损失self_loss为:

\[self\_loss = \left\{ \begin{aligned} & 2 * (elem - 1) & \mbox{($elem >= 1$)} \ & 0 & \mbox{($elem = 0$)} \ \end{aligned} \right. \]

??当某个位置的叠放立方体前后左右有其他叠放立方体,这个叠放立方体和相邻叠放立方体之间也会有一些面被”盖住“,产生表面积的损失。若相邻两个叠放立方体叠放数量分别为elem_1elem_2,则损失by_loss为:

\[by\_loss = \min (elem_1, elem_2) \]

??因此某位置叠放立方体露出的表面积则为:

\[6 - self\_loss - by\_loss \]

-ac代码-

class Solution:

    def _by_loss(self, elem, i_, j_, grid):
        if i_ < 0 or j_ < 0 or i_ >= len(grid) or j_ >= len(grid):
            return 0
        else:
            return min(elem, grid[i_][j_])

    def by_loss(self, elem, i, j, grid):
        return (self._by_loss(elem, i, j + 1, grid)
            + self._by_loss(elem, i, j - 1, grid)
            + self._by_loss(elem, i + 1, j, grid)
            + self._by_loss(elem, i - 1, j, grid)
        )

    def self_loss(self, elem):
        return 2 * (elem - 1) if elem >= 1 else 0

    def surfaceArea(self, grid: List[List[int]]) -> int:
        surface = 0
        for i in range(len(grid)):
            for j in range(len(grid)):
                elem = grid[i][j]

                surface += 6 * elem - self.self_loss(elem) - self.by_loss(elem, i, j, grid)

        return surface

-复杂度-

  • \(T(n) = O(n^2)\)
  • \(S(n) = O(1)\)

Leetcode daily 20/03/26 三维形体的表面积

原文:https://www.cnblogs.com/Chunngai/p/12573531.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!