代码随想录算法训练营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 0grid[i][j] = 2ans = 1for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:ans += dfs(i + di, j + dj)return ans ans = 0for 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] = tarea[t] += 1for 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 + 1dfs(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 = 1connected = {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