Asteroid Collision

Q: Qual é a complexidade de tempo da colisão de asteroides?

Tempo O(n) e espaço O(n) com uma pilha de sobreviventes, já que cada asteroide é empilhado e desempilhado no máximo uma vez. Percorrer a linha novamente após cada colisão custa O(n²) .

Q: Por que uma pilha é a estrutura de dados certa para a colisão de asteroides?

Um novo asteroide só pode alcançar os sobreviventes mais próximos dele, e os encontra do mais novo ao mais antigo. Isso é último a entrar, primeiro a sair. O que estiver na pilha no final não poderá mais colidir, então essa é a linha final.

Q: É possível resolver Colisão de Asteroides em O(1) de espaço extra?

Sim, se você puder sobrescrever a entrada. Use o início do array como pilha: mantenha um índice de gravação top , compare com asteroids[top-1] e retorne as primeiras top entradas.

MédioPilha

+10

Uma fileira de asteroides voa ao longo de uma linha, todos na mesma velocidade. Cada valor em asteroids descreve um asteroide: seu valor absoluto representa seu tamanho, e seu sinal indica sua direção: positivo para a direita e negativo para a esquerda.

Quando um asteroide que se move para a direita encontra um que se move para a esquerda, eles colidem. O menor explode; se tiverem o mesmo tamanho, ambos explodem. Asteroides que se movem na mesma direção nunca se encontram. Retorne os asteroides que restarem após todas as colisões, na ordem original. O resultado pode estar vazio.

Função

asteroidCollision(asteroids: integer-array) → integer-array

asteroidsinteger-array: os asteroides da esquerda para a direita, sinal para a direção, valor absoluto para o tamanho
Retornainteger-array: os asteroides restantes, da esquerda para a direita, possivelmente nenhum

Restrições

1 ≤ asteroids.length ≤ 10⁴
-1000 ≤ asteroids[i] ≤ 1000
asteroids[i] ≠ 0

Exemplos

Entrada: asteroids = [4, 9, -6, 2, -3]
Saída: [4, 9]
Explicação: 9 encontra -6 e vence. 2 encontra -3 e explode, e então -3 voa em direção a 9 e também explode. Nada mais se move em direção a nada, então 4 e 9 sobram.

Para ir além

A pilha responde quais asteroides sobrevivem. Como você também poderia informar, para cada asteroide que explode, o índice do asteroide que o destruiu?

Solução

Um asteroide que se move para a esquerda pode destruir uma longa sequência de asteroides que se movem para a direita, e cada colisão pode expor um novo par que colidirá em seguida. Um novo asteroide sempre encontra primeiro o sobrevivente mais recente, então uma pilha de sobreviventes resolve todas as colisões em uma única passagem.

Resolva uma falha por vez

Correta, mas não termina nos maiores testes

Intuição

Dois asteroides colidem exatamente quando um asteroide que se move para a direita está imediatamente à esquerda de um que se move para a esquerda. Encontre o primeiro par assim, resolva a colisão e examine novamente a partir da esquerda. Quando não houver mais nenhum par, nada mais colidirá e a fileira será a resposta.

A ordem de resolução não importa: dois asteroides adjacentes que se movem um em direção ao outro colidem antes que qualquer um deles possa colidir com outro.

Cada colisão exige uma nova varredura e a remoção de um asteroide do meio da fileira. Com 9,999 asteroides pequenos que se movem para a direita, seguidos por -1000, cada varredura percorre a fileira para destruir um asteroide que se move para a direita: cerca de 5 × 10^7 etapas.

Algoritmo

Copie a linha para que você possa remover os asteroides dela.
Examine da esquerda para encontrar o primeiro índice i em que row[i] > 0 e row[i+1] < 0.
Se não houver nenhum, retorne a linha.
Caso contrário, remova o menor dos dois ou ambos se tiverem o mesmo tamanho e examine novamente.

def asteroidCollision(asteroids):
    row = list(asteroids)
    while True:
        # A crash happens where a right-mover is directly followed by a left-mover.
        hit = -1
        for i in range(len(row) - 1):
            if row[i] > 0 and row[i + 1] < 0:
                hit = i
                break
        if hit == -1:
            return row
        right, left = row[hit], -row[hit + 1]
        if right > left:
            del row[hit + 1]
        elif right < left:
            del row[hit]
        else:
            del row[hit:hit + 2]

Pilha de sobreviventes

Intuição

Mantenha os sobreviventes até agora em uma pilha. Ela nunca contém um asteroide que se move para a direita seguido por um que se move para a esquerda, pois esse par já teria colidido; portanto, ela consiste em alguns asteroides que se moveram para a esquerda e escaparam, seguidos por asteroides que se movem para a direita.

Um novo asteroide que se move para a direita se afasta de tudo que está na pilha, então você o empilha. Um novo asteroide que se move para a esquerda vai em direção aos asteroides que se movem para a direita no topo e encontra primeiro o mais recente, então o topo é o único asteroide que ele pode atingir em seguida. No primeiro exemplo, -3 desempilha 2 e depois explode ao colidir com 9, e a pilha [4, 9] é a resposta na ordem original.

Cada asteroide é empilhado no máximo uma vez e desempilhado no máximo uma vez, então a passagem é O(n), mesmo quando um asteroide que se move para a esquerda elimina uma longa sequência.

Algoritmo

Comece com uma pilha vazia de asteroides sobreviventes.
Para cada asteroide, se ele se mover para a direita, coloque-o na pilha e continue.
Se ele se mover para a esquerda, remova do topo os asteroides que se movem para a direita enquanto forem menores que ele.
Se o elemento do topo agora for um asteroide que se move para a direita e tiver o mesmo tamanho, remova-o e descarte o novo asteroide. Se o elemento do topo for um asteroide maior que se move para a direita, descarte o novo asteroide. Caso contrário, coloque-o na pilha.
Retorne a pilha da base ao topo.

def asteroidCollision(asteroids):
    survivors = []  # the row so far, after every crash it caused
    for rock in asteroids:
        alive = True
        # Only a left-mover can hit something: a right-mover on top of the stack.
        while alive and rock < 0 and survivors and survivors[-1] > 0:
            top = survivors[-1]
            if top < -rock:
                survivors.pop()        # the right-mover is smaller and explodes
            elif top == -rock:
                survivors.pop()        # same size: both explode
                alive = False
            else:
                alive = False          # the right-mover is bigger: the new one explodes
        if alive:
            survivors.append(rock)
    return survivors

Armadilhas e casos extremos

Tratar um objeto que se move para a esquerda seguido de um que se move para a direita como uma colisão. Em [-2, -7, 3, 8], os grupos se afastam e os quatro sobrevivem.
Usar if em vez de while para remover os elementos. Em [1, 2, 3, 4, 5, -15], o objeto que se move para a esquerda destrói todos os cinco objetos que se movem para a direita e sobrevive.
Não tratar o caso de igualdade. [6, -6] deve remover 6 e descartar -6, deixando um resultado vazio.
Adicionar à pilha um objeto que se move para a esquerda, mas foi destruído. Em [9, -6], -6 explode e não deve ser colocado na pilha; mantenha uma flag para indicar se ele ainda está vivo.

Perguntas frequentes3

Qual é a complexidade de tempo da colisão de asteroides?

Tempo O(n) e espaço O(n) com uma pilha de sobreviventes, já que cada asteroide é empilhado e desempilhado no máximo uma vez. Percorrer a linha novamente após cada colisão custa O(n²).

Por que uma pilha é a estrutura de dados certa para a colisão de asteroides?

Um novo asteroide só pode alcançar os sobreviventes mais próximos dele, e os encontra do mais novo ao mais antigo. Isso é último a entrar, primeiro a sair. O que estiver na pilha no final não poderá mais colidir, então essa é a linha final.

É possível resolver Colisão de Asteroides em O(1) de espaço extra?

Sim, se você puder sobrescrever a entrada. Use o início do array como pilha: mantenha um índice de gravação top, compare com asteroids[top-1] e retorne as primeiras top entradas.

def asteroidCollision(asteroids):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

asteroids = [4, 9, -6, 2, -3]

Saída Esperada

[4, 9]