Golang Юниор

📌 Задача с leetcode. Max Area of Island

Максимальная площадь острова

Сложность: Средняя

Условие задачи:

Дан двумерный массив размера m x n. "1" отвечает за сушу, "0" - за океан. Необходимо опеределить максмимальную площадь острова из островов, расположенных на карте.

Островом считается территория, образованная из "1", расположенных сверху, справа, снизу и слева относительно друг друга.

Пример:

Ввод: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Вывод: 6

Ввод: grid = [[0,0,0,0,0,0,0,0]]

Вывод: 0

Решение

func maxAreaOfIsland(grid [][]int) int {
rows := len(grid)
if rows == 0 {
return 0
}

cols := len(grid[0])

var dfs func(grid [][]int, x, y, r, c, area int) int
dfs = func(grid [][]int, x, y, r, c, area int) int {
if x < 0 || y < 0 || x >= r || y >= c || grid[x][y] != 1 {
return area
}
grid[x][y] = 2

return 1 + dfs(grid, x+1, y, r, c, area) + dfs(grid, x, y+1, r, c, area) + dfs(grid, x-1, y, r, c, area) + dfs(grid, x, y-1, r, c, area)
}

maxArea := 0
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
area := dfs(grid, i, j, rows, cols, 0)
maxArea = int(math.Max(float64(area), float64(maxArea)))
}
}
return maxArea
}

Временная сложность: O(N*M)
Пространственная сложность: O(1)

Пишите свое решение в комментариях👇

www.tgoop.com/golangprofi/329

3.3K viewsAug 23, 2023 at 05:40

📌 Задача с leetcode. Max Area of Island

Максимальная площадь острова

Сложность: Средняя

Условие задачи:

Дан двумерный массив размера m x n. "1" отвечает за сушу, "0" - за океан. Необходимо опеределить максмимальную площадь острова из островов, расположенных на карте.

Островом считается территория, образованная из "1", расположенных сверху, справа, снизу и слева относительно друг друга.

Пример:

Ввод: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Вывод: 6

Ввод: grid = [[0,0,0,0,0,0,0,0]]

Вывод: 0

Решение

func maxAreaOfIsland(grid [][]int) int {
rows := len(grid)
if rows == 0 {
return 0
}

cols := len(grid[0])

var dfs func(grid [][]int, x, y, r, c, area int) int
dfs = func(grid [][]int, x, y, r, c, area int) int {
if x < 0 || y < 0 || x >= r || y >= c || grid[x][y] != 1 {
return area
}
grid[x][y] = 2

return 1 + dfs(grid, x+1, y, r, c, area) + dfs(grid, x, y+1, r, c, area) + dfs(grid, x-1, y, r, c, area) + dfs(grid, x, y-1, r, c, area)
}

maxArea := 0
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
area := dfs(grid, i, j, rows, cols, 0)
maxArea = int(math.Max(float64(area), float64(maxArea)))
}
}
return maxArea
}

Временная сложность: O(N*M)
Пространственная сложность: O(1)

Пишите свое решение в комментариях👇

BY Golang Юниор