leetcode 463. Island Perimeter
2023-09-14 09:11:53 时间
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
Example:
[[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]] Answer: 16 Explanation: The perimeter is the 16 yellow stripes in the image below:
我的解法:就是数数而已
class Solution(object): def islandPerimeter(self, grid): """ :type grid: List[List[int]] :rtype: int """ # for each element in island, calculate stripes and sum them row = len(grid) col = len(grid[0]) ans = 0 for i in range(0, row): for j in range(0, col): if grid[i][j] == 1: if i==0 or grid[i-1][j] == 0: ans += 1 if i==row-1 or grid[i+1][j] == 0: ans += 1 if j==0 or grid[i][j-1] == 0: ans += 1 if j==col-1 or grid[i][j+1]==0: ans += 1 return ans
更简单的做法,统计为1的矩形个数x,以及上下和左右相邻的边数y,结果为4x-2y
class Solution(object): def islandPerimeter(self, grid): """ :type grid: List[List[int]] :rtype: int """ # for each element in island, calculate stripes and sum them row = len(grid) col = len(grid[0]) ans = 0 for i in range(0, row): for j in range(0, col): if grid[i][j] == 1: ans += 4 if i>0 and grid[i-1][j] == 1: ans -= 2 if j>0 and grid[i][j-1] == 1: ans -= 2 return ans
还有一种DFS版本,
class Solution(object): def islandPerimeter(self, grid): """ :type grid: List[List[int]] :rtype: int """ # for each element in island, calculate stripes and sum them row = len(grid) col = len(grid[0]) self.ans = 0 def dfs(grid,i,j): if i<0 or i>=row or j<0 or j>=col: return if grid[i][j] == 0: return if grid[i][j] == 1: grid[i][j] = -1 if i==0 or grid[i-1][j] == 0: self.ans += 1 if i==row-1 or grid[i+1][j] == 0: self.ans += 1 if j==0 or grid[i][j-1] == 0: self.ans += 1 if j==col-1 or grid[i][j+1]==0: self.ans += 1 dfs(grid, i-1, j) dfs(grid, i+1, j) dfs(grid, i, j-1) dfs(grid, i, j+1) for i in range(0, row): for j in range(0, col): if grid[i][j] == 1: dfs(grid, i, j) return self.ans
DFS的代码结构:
dfs(xxx):
process(xxx.val)
dfs(xxx.left)
dfs(xxx.right)
也就和树的深度优先,先序遍历类似!
相关文章
- Java实现 LeetCode 665 非递减数列(暴力)
- Java实现 LeetCode 541 反转字符串 II(暴力大法)
- Java实现 LeetCode 454 四数相加 II
- Java实现 LeetCode 414 第三大的数
- Java实现 LeetCode 405 数字转换为十六进制数
- Java实现 LeetCode 297 二叉树的序列化与反序列化
- Java实现 LeetCode 233 数字 1 的个数
- Java实现 LeetCode 127 单词接龙
- Java实现 LeetCode 14 最长公共前缀
- 【刷题】【LeetCode】007-整数反转-easy
- Python 刷Leetcode题库,顺带学英语单词(13)
- 【Leetcode刷题Python】191. 位1的个数
- 【Leetcode刷题Python】剑指 Offer 09. 用两个栈实现队列
- 【461】汉明距离 【LeetCode】