Python вопросы с собеседований

🖥 Задача с 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



Решение



Сlass Solution:

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

rows,cols = len(grid),len(grid[0])

visited = [[False for j in range(cols)] for i in range(rows)]

def dfs(i,j):

if i<0 or i>= rows or j<0 or j>= cols or grid[i][j]==0 or visited[i][j]:

return 0

visited[i][j] = True

count = 1

count += dfs(i+1,j)

count += dfs(i-1,j)

count += dfs(i,j+1)

count += dfs(i,j-1)

return count



ans = 0

for i in range(rows):

for j in range(cols):

if grid[i][j]==1:

count = dfs(i,j)

ans = max(count,ans)

return ans





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



@python_job_interview