岛周长算法太慢

-2

我正在从LeetCode的岛周边问题，虽然我有一个工作解决方案，它只通过5817/5833测试用例。我认为这是成功的，但显然它不足以处理这些非常庞大的“岛屿”，如果我不明白是什么导致了性能问题，它会唠叨我。对于那些不熟悉“岛周边”问题的人，这里有一个指向LeetCode页面的链接。岛周长算法太慢

Island Perimeter Problem

我已经解决Python中的问题与语言refamiliarize自己，希望教我一些新花样，所以它可能只是什么我做的低效，有人可以帮助我更好地。任何人都可以在效率方面看到以下算法的明显问题吗？

def islandPerimeter(self, grid): 
    """ 
    :type grid: List[List[int]] 
    :rtype: int 
    """ 
    start = self.locateIsland(grid) 
    return self.islandHelp(grid, start) 

def islandHelp(self, grid, start): 
    # get the perimeter of this position 
    p = self.getPerimeter(grid, start) 
    # mark this position as visited so we don't count it repeatedly 
    grid[start[0]][start[1]] = 2 
    # offsets to current positions to find land to the sides 
    sides = [[-1, 0], [0, 1], [1, 0], [0, -1]] 
    for side in sides: 
     newPos = [(start[0] + side[0]), (start[1] + side[1])] 
     if ((newPos[0] in range(len(grid))) and 
     (newPos[1] in range(len(grid[newPos[0]]))) and 
     (grid[newPos[0]][newPos[1]] == 1)): 
       # recursively find perimeter of connected land 
       p += self.islandHelp(grid, newPos) 
    return p 

def getPerimeter(self, grid, pos): 
    p = 0 
    # offsets to find the neighboring positions 
    sides = [[-1, 0], [0, 1], [1, 0], [0, -1]] 
    for side in sides: 
     if (((pos[0] + side[0]) in range(len(grid))) and 
      ((pos[1] + side[1]) in range(len(grid[pos[0] + side[0]])))): 
      if (grid[pos[0] + side[0]][pos[1] + side[1]] == 0): 
       # in bounds of grid, but not a land mass, add to perimeter 
       p += 1 
     else: 
      # out of bounds means edge of grid, add to perimeter 
      p += 1 
    return p 

def locateIsland(self, grid): 
    # iterate through the grid to find a 1 and use that as start position 
    for r in range(len(grid)): 
     for c in range(len(grid[r])): 
      if (grid[r][c] == 1): 
       return (r, c) 
    return (-1, -1)

来源

2017-05-25 Darin Beaudreau

试着做没有递归，回溯和所有。把事情简单化。 –

给定的链接不会导致对问题的描述。请提供。可能是轮廓跟踪？ http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/alg.html –

当你做这样的检查：包含整数[

Python的创建大小LEN（格）的列表：

(pos[0] + side[0]) in range(len(grid))

下面的事情正在发生0,1,2,3，...]
Python会将您的号码（本例中为pos [0] + side [0]）和teger在列表中，将其与该整数进行比较以查看它是否相同。

如果所有你想知道的是如果数字小于网格的长度，这是不高效的！您可以替换符合

(pos[0] + side[0]) >= 0 and (pos[0] + side[0]) < len(grid)

得到同样的效果，可在更短的时间。我做了这个改变，并检查它是否通过了所有的情况。

来源

2017-05-25 13:21:45 Shiro

这很奇怪......我做了同样的事情，现在我提交的细节说我通过了5833/5833测试用例，但它仍然说时间超出限制并拒绝我的提交。 –

我再次提交它，并接受它...很高兴知道我可以成功或失败，取决于我的算法的性能服务器... –

岛周长算法太慢

回答

相关问题