24 de Março
Número de ilhas
Como enxergar cada celula como no de um grafo e usar busca em profundidade ou em largura para consumir uma ilha inteira de uma vez.
Grafos em Grade Intermediario 22 min TypeScript
Dada uma grade 2D composta por '1' (terra) e '0' (agua), retorne o número de ilhas.
Uma ilha e formada por terras conectadas horizontal ou verticalmente.
Exemplo:
Input:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
Output: 3
O que perceber antes de codar
- Diagonal não conecta ilha.
- O problema pede contar componentes conectados.
- Assim que você consome uma ilha inteira, ela não deve ser contada de novo.
Erros comuns
- contar cada celula de terra separadamente
- esquecer de marcar visitados antes de explorar vizinhos
Passo 1 - Parar de ver isso como só uma matriz
Esse problema fica mais simples quando você troca o nome mental dele.
Em vez de "matriz de 1 e 0", pense:
- cada celula de terra e um no
- vizinhos em cima, baixo, esquerda e direita sao arestas
Agora você esta contando componentes conectados.
Passo 2 - Escrever a regra de contagem
Se você esta varrendo a grade e encontra uma terra ainda não visitada:
- achou uma ilha nova
- incrementa a resposta
- consome toda a ilha antes de seguir
Passo 3 - Fazer a versão inicial com visitados
Uma versão inicial boa e:
- manter um
conjunto hashde visitados - quando encontra terra nova, rodar
busca em profundidade (DFS) - marcar toda a componente
Isso deixa a estrutura do problema bem explicita.
Passo 4 - Perceber que a própria grade pode virar o visitado
Em muitos casos, você não precisa de estrutura extra.
Pode marcar a terra já processada como agua e continuar.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function numIslands(grid: string[][]): number {
// sua solução aqui
return 0
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(rows * cols)
Espaço: O(rows * cols)
Solução 1 - Busca em profundidade (DFS) com conjunto hash de visitados
Boa versão inicial para deixar claro que o problema e de componente conectada.
export function numIslands(grid: string[][]): number {
const rows = grid.length
const cols = grid[0]?.length ?? 0
const visited = new Set<string>()
let islands = 0
function dfs(row: number, col: number) {
if (
row < 0 ||
row >= rows ||
col < 0 ||
col >= cols ||
grid[row][col] === '0'
) {
return
}
const key = `${row},${col}`
if (visited.has(key)) {
return
}
visited.add(key)
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (grid[row][col] === '1' && !visited.has(`${row},${col}`)) {
islands += 1
dfs(row, col)
}
}
}
return islands
}Funciona bem. Mas da para usar a própria grade como marcador.
Solução 2 - Busca em profundidade (DFS) transformando a grade na estrutura de visitados
Agora o visitado fica embutido no próprio input.
export function numIslands(grid: string[][]): number {
const rows = grid.length
const cols = grid[0]?.length ?? 0
let islands = 0
function dfs(row: number, col: number) {
if (
row < 0 ||
row >= rows ||
col < 0 ||
col >= cols ||
grid[row][col] === '0'
) {
return
}
grid[row][col] = '0'
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (grid[row][col] === '1') {
islands += 1
dfs(row, col)
}
}
}
return islands
}O ponto forte aqui e a leitura de componente conectada, não o fato de ser busca em profundidade (DFS) especificamente.
O que dizer na entrevista
Uma explicação curta e boa seria:
Eu trato cada terra como no de um grafo em grade. Quando encontro uma terra ainda não visitada, isso significa uma nova ilha. Entao incremento a resposta e faco
busca em profundidade (DFS)para consumir toda a componente conectada. Assim cada celula e visitada no máximo uma vez.
Isso mostra que você:
- traduziu o formato para um modelo de grafo
- separou a regra de contagem da regra de exploração
- explicou por que a resposta não duplica ilhas
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- percorrer grade com
busca em largura (BFS)oubusca em profundidade (DFS) - contar componentes conectados
- consumir uma area conectada inteira antes de seguir
- tratar celulas como nos e adjacencia como arestas
O ponto não e decorar esse problema.
O ponto e aprender a ver grafos escondidos em grades.