岛屿问题的最大面积 leetcode python

问题描述 投票:2回答:1

该问题的内容如下。给定一个由0和1组成的非空的二维阵列网格,一个岛屿是一组1(代表陆地)在4个方向上(水平或垂直)连接起来,你可以假设网格的4条边都被水包围。

在给定的二维数组中,求一个岛的最大面积。如果没有岛屿,最大面积为0。

class Solution:

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


        for x in range(0, a):
            b = len(grid[x])
            for y in range(0 , b):
                if grid[x][y] == "1":
                    self.dfs(grid , x , y)

        return count

    def dfs(self,grid, i, j):
        count = 0

        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == "0" or grid[i][j] == "2":
            return 

        grid[i][j] = "2"
        count += 1

        self.dfs(grid , i-1 , j)
        self.dfs(grid , i+1, j)
        self.dfs(grid, i , j-1)
        self.dfs(grid , i , j+1)

我正在尝试使用深度优先搜索方法来寻找邻居。但是,我不知道如何在找到 "1 "时正确地递增计数,以及输出总计数。谁能帮帮我?

python
1个回答
0
投票

为了能够在递归函数中增加计数,它应该是一个类变量或全局变量。你还试图在每次进入dfs时将其重置为0,这是不对的,因为你的dfs函数会调用自己并将该计数重置为0。 你的基本想法是好的,你将你已经访问过的部分标记为 "2"。唯一还可以改变的是你对边缘的检查。问题是你可以假设边缘都是0,所以你可以直接从位置1,1开始迭代,而不是0,0,因为你永远不会通过做DFS到达地图之外。

你应该重置计数的地方是在maxAreaOfIsland函数中,每当你发现一个'1'的瓷砖时。你也可以在dfs之后检查它是否大于你找到的最大值。

class Solution:
    def __init__(self):
        self._count = 0   # You need the count to be visible for both functions, so you can declare it here
        self._maxCount = 0 # Max count doesn't have to be declared here, you can also declare it inside maxAreaOfIsland   

    def maxAreaOfIsland(self, grid):
        a = len(grid)


        for x in range(0, a):
            b = len(grid[x])
            for y in range(0 , b):
                if grid[x][y] == "1":
                    self._count = 0   # Here you reset the count
                    self.dfs(grid , x , y)
                    if self._count > self._maxCount:  # Here you check if it's greater than the max
                        self._maxCount = self._count

        return self._maxCount

    def dfs(self,grid, i, j):

        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == "0" or grid[i][j] == "2":
            return 

        grid[i][j] = "2"
        self._count += 1 # Here you increment the count

        self.dfs(grid , i-1 , j)
        self.dfs(grid , i+1, j)
        self.dfs(grid, i , j-1)
        self.dfs(grid , i , j+1)

0
投票

你可以在没有递归性的情况下,为陆地上的位置建立一个坐标字典(集合)。 然后为每个连接到右边或低于其他陆地位置的陆地位置合并这些集合。 其结果将是所有连接的位置的共同位置集。 这些集合中最大的一组的长度将是最大的岛屿的面积。

def maxIsland(grid):
    rows,cols = len(grid),len(grid[0])
    land      = { (r,c):{(r,c)} for r in range(rows) for c in range(cols) if grid[r][c] }
    for (r,c) in list(land):
        for nr,nc in [(r+1,c),(r,c+1)]:            # Positions below/right 
            if (nr,nc) not in land:  continue      # connecting land 
            if land[r,c] is land[nr,nc]: continue  # skip already merged
            land[r,c].update(land[nr,nc])          # Merge set of positions 
            for (lr,lc) in land[nr,nc]: 
                land[lr,lc] = land[r,c]            # Propagate merged set to all
    return max(map(len,land.values()))             # return size of largest set

输出。

world = [ "0000000000000",
          "0111000000111",
          "0101110000111",
          "0100111100111",
          "0100000100000",
          "0101001110000",
          "0111001110000" ]
world = [ list(map(int,row)) for row in world ]

print( maxIsland(world) ) # 25

对于一个更基本的方法,你可以从一组陆地坐标出发,逐步取出连接成岛屿的坐标,同时测量岛屿的大小。 岛屿可以通过扩展一个陆地坐标,增加未被发现的邻居,并扩展新增加的岛屿位置来形成。

def maxIsland(grid):
    rows,cols = len(grid),len(grid[0])
    land      = { (r,c) for r in range(rows) for c in range(cols) if grid[r][c] }
    result    = 0
    while land:                    # find new islands in uncharted land
        island    = [land.pop()]           # pick a coordinate to expand into an island
        expanding = 0                      # will expand coordinates added by expansion
        while expanding<len(island):
            r,c = island[expanding]                         # expand added coordinate 
            neighbours = {(r+1,c),(r-1,c),(r,c+1),(r,c-1)}  # candidate coordinates
            island    += list(land & neighbours)            # add uncharted land to island
            land      -= neighbours                         # remove from uncharted land
            expanding += 1                                  
        result = max(result,len(island))   # track largest island
    return result

注意:在大网格上,这个运行速度会比第一个快很多

© www.soinside.com 2019 - 2024. All rights reserved.