代码随想录算法训练营Day58

力扣695.岛屿的最大面积【medium】
力扣827.最大人工岛【hard】

一、力扣695.岛屿的最大面积【medium】

题目链接：力扣695.岛屿的最大面积

视频链接：代码随想录

1、思路

• 和岛屿数量那道题很像，只是递归这边要多一个怎么计算面积，就是把一格一格的1累加起来
• 时间复杂度：$O(n\ast m)$
• 空间复杂度：$O(n\ast m)$

2、代码

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def dfs(i,j) -> int:
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
                return 0
            grid[i][j] = 2
            ans = 1
            for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                ans += dfs(i + di, j + dj)
            return ans 
        ans = 0
        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                ans = max(ans, dfs(i,j))
        return ans

二、力扣827.最大人工岛【hard】

题目链接：力扣827.最大人工岛

视频链接：代码随想录
题解链接：力扣官方题解

1、思路

• 先算出来并按岛屿标记面积，这一步是递归实现，记录面积用的是哈希表–字典Counter
• 最后一次的双层fou循环，时间的建造人工岛，将某个0 变成1，这一步也用了set来避免碰到重复岛屿
• 时间复杂度：$O(n)$

2、代码

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        tag = [[0] * n for _ in range(n)]
        area = Counter()
        def dfs(i:int,j:int) -> None:
            tag[i][j] = t
            area[t] += 1
            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                if 0 <= x < n and 0 <= y < n and grid[x][y] and tag[x][y] == 0:
                    dfs(x,y)
        
        for i, row in enumerate(grid):
            for j , c in enumerate(row):
                if c and tag[i][j] == 0:
                    t = i * n + j + 1
                    dfs(i,j)
        ans = max(area.values(), default = 0)

        for i, row in enumerate(grid):
            for j , c in enumerate(row):
                if c == 0:
                    ner_area = 1
                    connected = {0}
                    for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                        if 0 <= x < n and 0 <= y < n and tag[x][y] not in connected:
                            ner_area += area[tag[x][y]]
                            connected.add(tag[x][y])
                    ans = max(ans, ner_area)
        return ans