Leetcode 200. Количество островов TLE - PullRequest
Новая
       27

Leetcode 200. Количество островов TLE

0 голосов
/ 05 февраля 2019

Ссылка на вопрос: https://leetcode.com/problems/number-of-islands/

Учитывая 2-мерную карту сетки «1 (земля) и» 0 (вода), подсчитайте количество островов.Остров окружен водой и образован соединением соседних земель по горизонтали или вертикали.Вы можете предположить, что все четыре края сетки окружены водой.

Пример 1:

Ввод: 

11110
11010
11000
00000

Выход: 1

Моя логика заключается в том, чтобы просто делать DFS из каждого узла и отслеживать подключенные компоненты.Получаю лимит времени (TLE) для 46-го теста, может кто-нибудь помочь мне оптимизировать этот код?

class Решение (объект): 

def numIslands(self, grid):

    def in_grid(x, y):
        return 0 <= x < len(grid) and 0 <= y < len(grid[0])

    def neighbours(node):
        p, q = node
        dir = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        return [(x, y) for x, y in [(p + i, q + j) for i, j in dir] if in_grid(x, y)]

    def dfs(node):
        visited.append(node)
        for v in neighbours(node):
            if grid[v[0]][v[1]]== "1" and v not in visited:
                dfs(v)

    components = 0
    visited = []
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            node = (i, j)
            if grid[i][j] == "1" and node not in visited:
                components += 1
                dfs(node)

    return components

Ответы [ 2 ]

0 голосов
/ 16 июля 2019

Причина, по которой вы получаете TLE, заключается в том, что вы используете список для отслеживания посещенных узлов.Поиск значения в списке в худшем случае занимает время O (n).

Оптимальным является сохранение статуса индекса посещенного / не посещенного узла в виде двумерной матрицы, содержащей логические значения, или O /1 целое числоЭто приводит к постоянному времени доступа O (1) для нахождения посещенного / не посещенного статуса узла. 

class Solution {

    boolean isSafe(char[][] grid, int[][] visited, int i, int j)
    {
        int n = grid.length;
        int m = grid[0].length;

        if((i<0 || i>n-1) || (j<0 || j>m-1))
            return false;

        return visited[i][j] == 0 && grid[i][j] == '1';
    }

    void DFS(char[][] grid, int[][] visited, int i, int j)
    {
        visited[i][j] = 1; //marked visited

        int[] row = {-1, 0, 1, 0};
        int[] column = {0, 1, 0, -1};

        for(int k = 0; k<4; k++)
        {
            if(isSafe(grid, visited, i+row[k], j+column[k]))
            {
                DFS(grid, visited, i+row[k], j+column[k]);
            }
        }
    }

    int DFSUtil(char[][] grid)
    {
        int count = 0;

        if(grid == null || grid.length == 0)
            return count;

        int n = grid.length; //rows
        int m = grid[0].length; //columns

        int[][] visited = new int[n][m];

        for(int i = 0; i<n; i++)
            for(int j = 0; j<m; j++)
            {
                if(grid[i][j]=='1' && visited[i][j] == 0)
                {
                    DFS(grid, visited, i, j);
                    count++;
                }
            }

        return count;
    }

    public int numIslands(char[][] grid) {

        int result = DFSUtil(grid);

        return result;
    }
}
0 голосов
/ 09 февраля 2019

Я думаю, что ваш подход правильный.Однако вы используете visited в качестве list, что требует O(n) для поиска значения.Таким образом, его общая временная сложность составляет O(N^2).Я бы предложил использовать set вместо list, который является хеш-таблицей.

Необходимо пересмотреть только две части:

  • visited = [] -> visited = set()
  • visited.append(node) -> visited.append(node)

Я подтвердил, что это принято.Теперь node not in visited занимает O(1), поэтому общая временная сложность составляет O(N).

% Как и большинство других проблем LeetCode, формулировка задачи не дает никакой информации о входных данных.Но так как ваш код TLE, мы можем предположить, что мы не можем решить его с временной сложностью O(n^2).

...