Leetcode 695/200. Max Area of Island

Posted on | | 阅读数
Words count in article: 424 | Reading time ≈ 2

Question1

Solution

首先考虑怎么计算面积。考虑用递归。如果当前元素是1，那么我们就要考虑其上下左右四个元素是否是1，以及更外面的元素是否是1.同时在计算的时候，要将当前元素赋值为0，防止重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def calArea(self, grid, i, j):
        if i < 0 or j < 0 or i > len(grid) - 1 or j > len(grid[0]) - 1:
            return 0
        if grid[i][j] == 0:
            return 0
        else:
            grid[i][j] = 0 # 防止重复计算
            a = 1 + self.calArea(grid, i-1, j) + self.calArea(grid, i+1, j)
            + self.calArea(grid, i, j-1) + self.calArea(grid, i, j+1)
            
            return a
    
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        area = 0
        rows = len(grid)
        cols = len(grid[0])
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    area = max(area, self.calArea(grid, i, j))
        return area

精简

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def calArea(self, grid, i, j):
        if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j]:
            grid[i][j] = 0
            a = 1 + self.calArea(grid, i-1, j) + self.calArea(grid, i+1, j)
            + self.calArea(grid, i, j-1) + self.calArea(grid, i, j+1)
            
            return a
        return 0
    
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        area = 0
        rows, cols = len(grid), len(grid[0])
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    area = max(area, self.calArea(grid, i, j))
        return area

Question2

Solution

和上面类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def calArea(self, grid, i, j):
        if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == "1":
            grid[i][j] = "0"
            self.calArea(grid, i-1, j)
            self.calArea(grid, i+1, j)
            self.calArea(grid, i, j-1)
            self.calArea(grid, i, j+1)
            return 1
        return 0
    
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:   #防止list
            return 0
        time = 0
        rows, cols = len(grid), len(grid[0])
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    time += self.calArea(grid, i, j)
        return time