Soluzione:Area massima dell'isola

Questo fa parte di una serie di spiegazioni sulla soluzione di Leetcode (indice). Se questa soluzione ti è piaciuta o l'hai trovata utile, metti mi piace questo post e/o voto favorevole il mio post sulla soluzione sui forum di Leetcode.

Problema #695 di Leetcode (Medio ):Area massima dell'isola

Descrizione:

(Vai a :Idea di soluzione || Codice :JavaScript | Pitone | Java | C++ )

Esempi:

Vincoli:

Idea:

(Vai a :Descrizione del problema || Codice :JavaScript | Pitone | Java | C++ )

Quindi possiamo semplicemente usare una semplice iterazione attraverso la griglia e cerca le isole. Quando troviamo un'isola, possiamo usare un ricorsivo funzione di supporto (trav ) per riassumere tutti i terreni collegati e ritorna la massa terrestre totale dell'isola.

Mentre attraversiamo l'isola, possiamo sostituire il 1 s con 0 s per evitare di "trovare" la stessa terra due volte. Possiamo anche tenere traccia dell'isola più grande trovata finora (ans ), e dopo la griglia è stato completamente attraversato, possiamo restituire un .

• Complessità temporale:O(N * M) dove N e M sono le lunghezze dei lati della griglia
• Complessità spaziale:O(L) dove L è la dimensione dell'isola più grande, che rappresenta il massimo stack di ricorsione
  • o O(N * M + L) se creiamo un N * M matrice per non modificare l'input

Codice JavaScript:

(Vai a :Descrizione del problema || Idea di soluzione )

var maxAreaOfIsland = function(grid) {
    let ans = 0, n = grid.length, m = grid[0].length
    const trav = (i, j) => {
        if (i < 0 || j < 0 || i >= n || j >= m || !grid[i][j]) return 0
        grid[i][j] = 0
        return 1 + trav(i-1, j) + trav(i, j-1) + trav(i+1, j) + trav(i, j+1)
    }
    for (let i = 0; i < n; i++) 
        for (let j = 0; j < m; j++)
            if (grid[i][j]) ans = Math.max(ans, trav(i, j))
    return ans
};

Codice Python:

(Vai a :Descrizione del problema || Idea di soluzione )

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans, n, m = 0, len(grid), len(grid[0])
        def trav(i: int, j: int) -> int:
            if i < 0 or j < 0 or i >= n or j >= m or grid[i][j] == 0: return 0
            grid[i][j] = 0
            return 1 + trav(i-1, j) + trav(i, j-1) + trav(i+1, j) + trav(i, j+1)
        for i, j in product(range(n), range(m)):
            if grid[i][j]: ans = max(ans, trav(i, j))
        return ans

Codice Java:

(Vai a :Descrizione del problema || Idea di soluzione )

class Solution {
    private int n, m;
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        n = grid.length;
        m = grid[0].length;
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++)
                if (grid[i][j] > 0) ans = Math.max(ans, trav(i, j, grid));
        return ans;
    }
    private int trav(int i, int j, int[][] grid) {
        if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] < 1) return 0;
        grid[i][j] = 0;
        return 1 + trav(i-1, j, grid) + trav(i, j-1, grid) + trav(i+1, j, grid) + trav(i, j+1, grid);
    }
}

Codice C++:

(Vai a :Descrizione del problema || Idea di soluzione )

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++)
                if (grid[i][j]) ans = max(ans, trav(i, j, grid));
        return ans;
    }
private:
    int n, m;
    int trav(int i, int j, vector<vector<int>>& grid) {
        if (i < 0 || j < 0 || i >= n || j >= m || !grid[i][j]) return 0;
        grid[i][j] = 0;
        return 1 + trav(i-1, j, grid) + trav(i, j-1, grid) + trav(i+1, j, grid) + trav(i, j+1, grid);
    }
};