【Leetcode】463. 岛屿的周长

一、题目描述

给定一个 $KaTeX parse error: Undefined control sequence: \x at position 4: row\̲x̲\col$ 的二维网格地图 $g r i d$ ，其中： $g r i d [i] [j] = 1$ 表示陆地， $g r i d [i] [j] = 0$ 表示水域。

网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖”指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为1的正方形。网格为长方形，且宽度和高度均不超过100。计算这个岛屿的周长。

示例 1：

在这里插入图片描述

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：
输入：grid = [[1]]
输出：4

示例 3：
输入：grid = [[1,0]]
输出：4

提示：
row == grid.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j] 为 0 或 1

二、解题过程

1、第一次尝试

1.1 代码如下

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        self.grid = grid
        self.rows = len(grid)
        self.cols = len(grid[0]) if self.rows > 0 else 0

        if self.rows <= 100 and self.cols <= 100:
            perimeter = 0

            for i in range(self.rows):
                for j in range(self.cols):
                    if self.grid[i][j] == 1:  # 当前格子是陆地
                        # 检查上方是否为水域或网格边界
                        if i == 0 or self.grid[i - 1][j] == 0:
                            perimeter += 1
                        # 检查下方是否为水域或网格边界
                        if i == self.rows - 1 or self.grid[i + 1][j] == 0:
                            perimeter += 1
                        # 检查左侧是否为水域或网格边界
                        if j == 0 or self.grid[i][j - 1] == 0:
                            perimeter += 1
                        # 检查右侧是否为水域或网格边界
                        if j == self.cols - 1 or self.grid[i][j + 1] == 0:
                            perimeter += 1

            return perimeter

1.2 运行情况
运行用时较长，内存消耗较多，复杂度为 $O (M n)$ 。
在这里插入图片描述

2、优化

要降低代码的复杂度，我们可以简化一些操作和避免不必要的变量存储。

改进点：

直接检查网格是否为空：通过 if not grid or not grid[0]: 提前处理空网格的情况，这样可以避免在后续计算中访问空列表。
减少不必要的变量存储：去掉了 self.grid, self.rows, self.cols 这些存储，直接在函数内部使用局部变量 grid, rows, cols。
保持逻辑清晰：代码逻辑与原版本一致，但去除了多余的代码行和变量，使得代码更加紧凑和易于阅读。

2.1 代码如下

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        perimeter = 0
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:  # 当前格子是陆地
                    # 上边界或上方为水域
                    if i == 0 or grid[i - 1][j] == 0:
                        perimeter += 1
                    # 下边界或下方为水域
                    if i == rows - 1 or grid[i + 1][j] == 0:
                        perimeter += 1
                    # 左边界或左侧为水域
                    if j == 0 or grid[i][j - 1] == 0:
                        perimeter += 1
                    # 右边界或右侧为水域
                    if j == cols - 1 or grid[i][j + 1] == 0:
                        perimeter += 1
 
        return perimeter

2.2 运行情况
运行用时缩短，内存消耗差不多，复杂度为 $O (M n)$ 。
在这里插入图片描述

3、第二次优化

可以转换个思路：逐行遍历方格，每行第一个陆地方格周长取4；后面若没有存在公共边，加4；存在一条公共边，减2；存在两条公共边，需减4。以示例1举例见下图。

在这里插入图片描述

3.1 代码如下

class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        perimeter = 0
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    perimeter += 4
                    if i - 1 >= 0 and grid[i - 1][j] == 1:
                        # 如果当前格子的上边一个格子是陆地，说明他们之间共享一条边，因此从周长中减去2
                        perimeter -= 2
                    if j - 1 >= 0 and grid[i][j - 1] == 1:
                        # 如果当前格子的左边一个格子是陆地，依然说明他们共享一条边，周长同样减少2
                        perimeter -= 2
 
        return perimeter