Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/892.html
892. Surface Area of 3D Shapes (Easy)
On a N * N
grid, we place some 1 * 1 * 1
cubes.
Each value v = grid[i][j]
represents a tower of v
cubes placed on top of grid cell (i, j)
.
Return the total surface area of the resulting shapes.
Example 1:
Input: [[2]] Output: 10
Example 2:
Input: [[1,2],[3,4]] Output: 34
Example 3:
Input: [[1,0],[0,2]] Output: 16
Example 4:
Input: [[1,1,1],[1,0,1],[1,1,1]] Output: 32
Example 5:
Input: [[2,2,2],[2,1,2],[2,2,2]] Output: 46
Note:
1 <= N <= 50
0 <= grid[i][j] <= 50
Solution 1.
// OJ: https://leetcode.com/problems/surface-area-of-3d-shapes/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
int surfaceArea(vector<vector<int>>& grid) {
int N = grid.size(), area = 0;
for (int i = 0; i < N; ++i) {
int prev = 0;
for (int j = 0; j < N; ++j) {
if (grid[i][j]) area += 2;
area += abs(grid[i][j] - prev);
prev = grid[i][j];
}
area += prev;
}
for (int i = 0; i < N; ++i) {
int prev = 0;
for (int j = 0; j < N; ++j) {
area += abs(grid[j][i] - prev);
prev = grid[j][i];
}
area += prev;
}
return area;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/surface-area-of-3d-shapes/
// Time: O(N^2)
// Space: O(1)
class Solution {
private:
int dirs[4][2] = { {0,1}, {-1,0}, {0,-1}, {1,0} };
public:
int surfaceArea(vector<vector<int>>& grid) {
int N = grid.size(), area = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!grid[i][j]) continue;
area += 2;
for (auto &dir : dirs) {
int x = i + dir[0], y = j + dir[1];
int h = x < 0 || x >= N || y < 0 || y >= N ? 0 : grid[x][y];
area += max(grid[i][j] - h, 0);
}
}
}
return area;
}
};
Java
-
class Solution { public int surfaceArea(int[][] grid) { int area = 0; int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int rows = grid.length, columns = grid[0].length; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { int cell = grid[i][j]; int curArea = cell == 0 ? 0 : cell * 4 + 2; for (int[] direction : directions) { int newRow = i + direction[0], newColumn = j + direction[1]; if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns) { int adjacent = grid[newRow][newColumn]; int overlapArea = Math.min(cell, adjacent); curArea -= overlapArea; } } area += curArea; } } return area; } }
-
// OJ: https://leetcode.com/problems/surface-area-of-3d-shapes/ // Time: O(N^2) // Space: O(1) class Solution { public: int surfaceArea(vector<vector<int>>& grid) { int N = grid.size(), area = 0; for (int i = 0; i < N; ++i) { int prev = 0; for (int j = 0; j < N; ++j) { if (grid[i][j]) area += 2; area += abs(grid[i][j] - prev); prev = grid[i][j]; } area += prev; } for (int i = 0; i < N; ++i) { int prev = 0; for (int j = 0; j < N; ++j) { area += abs(grid[j][i] - prev); prev = grid[j][i]; } area += prev; } return area; } };
-
class Solution: def surfaceArea(self, grid: List[List[int]]) -> int: ans = 0 for i, row in enumerate(grid): for j, v in enumerate(row): if v: ans += 2 + v * 4 if i: ans -= min(v, grid[i - 1][j]) * 2 if j: ans -= min(v, grid[i][j - 1]) * 2 return ans ############ class Solution(object): def surfaceArea(self, grid): """ :type grid: List[List[int]] :rtype: int """ area = 0 n = len(grid) for i in range(n): for j in range(n): if grid[i][j]: area += grid[i][j] * 4 + 2 if i: area -= min(grid[i][j], grid[i-1][j]) * 2 if j: area -= min(grid[i][j], grid[i][j-1]) * 2 return area