892.三次元形状の表面積(Python)
2295 ワード
タイトル
難易度:★☆☆☆タイプ:ジオメトリ、数学、2 D配列
N*Nのメッシュ上に、1*1*1の立方体を配置します.
各値v=grid[i][j]は、v個の正方体がセル(i,j)上に重畳されていることを示す.
最終シェイプの表面積を返します.
ヒント1<=N<=50 0<=grid[i][j]<=50
例
例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
に答える
この問題は「テーマ463.島の周長」と同じ種類で、2次元を3次元に拡張することに相当する.
ループ.タイトルは、検索範囲が50*50のグリッド(grid)であることを示しているので、各グリッドを巡って、これらのグリッドに四角柱があるかどうかを確認することができます.
表面積の処理.これはこの問題のポイントと難点であり、ある正方形(grid[i][j])に四角柱が存在する場合、四角柱の上下底面は遮ることができないため、最終的な結果は必ず上下底面を含み、遮る可能性のある部分は4方向の側面しかなく、側面が隣接する位置に角柱が存在する場合、現在の角柱の一部は必ず遮られ、遮る面積は両者の高さに依存する.
現在のプリズムgrid[i][j]寄与の表面積を計算した.
底面:まず2つの底面の面積を結果に追加します:ans=ans+2;側面:4つの隣接位置(i+1,j),(i−1,j),(i,j+1),(i,j−1)をそれぞれ考慮し、そのうちの1つの位置に高さhのプリズムが存在する場合、現在の高さgrid[i][j]のプリズムが遮蔽されている部分の高さはmin(h,grid[i][j])であり、grid[i][j]−min(h,grid[i][j])=max(0,grid[i][j]−h)の表面積に寄与し、ここでhは隣接するプリズムの高さであり、両者の接触面の面積とも考えられ、concatと定義される.
例えば[[1,5]]は、[0,0]の方格に高さ1の角柱Aを、[0,1]の方格に高さ5の角柱Bを、角柱Bが寄与する表面積を表す計算方法であり、2(2つの底面)+3*5(角柱が隣接しない3つの側面)+(5-1)(角柱Aに接する側面)=21である.
境界.あるプリズムが境界上にある場合、その周囲の4つの隣接方向を考察すると、1つの方向が碁盤の範囲を超えていることがわかり、この碁盤を超えた位置にはプリズムがない、すなわち、隣接位置と現在の接触面の面積concatがゼロであり、この面が寄与する表面積は実際には現在のプリズムの高さであると考えられる.
例えば、上記の例では、角柱Aの寄与の表面積は、2(2つの底面)+1(エッジの側面)+1(エッジの側面)+1(角柱が接していない側面)+0(角柱Bと接する側面)=5であり、2つの角柱の寄与表面積は21+5=26である.
エンコーディングプロセスは次のとおりです.
質問やアドバイスがあれば、コメントエリアへようこそ~
難易度:★☆☆☆タイプ:ジオメトリ、数学、2 D配列
N*Nのメッシュ上に、1*1*1の立方体を配置します.
各値v=grid[i][j]は、v個の正方体がセル(i,j)上に重畳されていることを示す.
最終シェイプの表面積を返します.
ヒント1<=N<=50 0<=grid[i][j]<=50
例
例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
に答える
この問題は「テーマ463.島の周長」と同じ種類で、2次元を3次元に拡張することに相当する.
ループ.タイトルは、検索範囲が50*50のグリッド(grid)であることを示しているので、各グリッドを巡って、これらのグリッドに四角柱があるかどうかを確認することができます.
表面積の処理.これはこの問題のポイントと難点であり、ある正方形(grid[i][j])に四角柱が存在する場合、四角柱の上下底面は遮ることができないため、最終的な結果は必ず上下底面を含み、遮る可能性のある部分は4方向の側面しかなく、側面が隣接する位置に角柱が存在する場合、現在の角柱の一部は必ず遮られ、遮る面積は両者の高さに依存する.
現在のプリズムgrid[i][j]寄与の表面積を計算した.
底面:まず2つの底面の面積を結果に追加します:ans=ans+2;側面:4つの隣接位置(i+1,j),(i−1,j),(i,j+1),(i,j−1)をそれぞれ考慮し、そのうちの1つの位置に高さhのプリズムが存在する場合、現在の高さgrid[i][j]のプリズムが遮蔽されている部分の高さはmin(h,grid[i][j])であり、grid[i][j]−min(h,grid[i][j])=max(0,grid[i][j]−h)の表面積に寄与し、ここでhは隣接するプリズムの高さであり、両者の接触面の面積とも考えられ、concatと定義される.
例えば[[1,5]]は、[0,0]の方格に高さ1の角柱Aを、[0,1]の方格に高さ5の角柱Bを、角柱Bが寄与する表面積を表す計算方法であり、2(2つの底面)+3*5(角柱が隣接しない3つの側面)+(5-1)(角柱Aに接する側面)=21である.
境界.あるプリズムが境界上にある場合、その周囲の4つの隣接方向を考察すると、1つの方向が碁盤の範囲を超えていることがわかり、この碁盤を超えた位置にはプリズムがない、すなわち、隣接位置と現在の接触面の面積concatがゼロであり、この面が寄与する表面積は実際には現在のプリズムの高さであると考えられる.
例えば、上記の例では、角柱Aの寄与の表面積は、2(2つの底面)+1(エッジの側面)+1(エッジの側面)+1(角柱が接していない側面)+0(角柱Bと接する側面)=5であり、2つの角柱の寄与表面積は21+5=26である.
エンコーディングプロセスは次のとおりです.
class Solution:
def surfaceArea(self, grid):
"""
:param grid: List[List[int]]
:return: int
"""
N = len(grid)
ans = 0 #
for r in range(N):
for c in range(N):
if grid[r][c]: #
ans += 2 #
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)): #
contact = grid[nr][nc] if 0 <= nr < N and 0 <= nc < N else 0 #
ans += max(grid[r][c] - contact, 0) #
return ans
質問やアドバイスがあれば、コメントエリアへようこそ~