Asteroid Collision
Rząd asteroid porusza się wzdłuż linii, wszystkie z taką samą prędkością. Każda wartość w asteroids opisuje jedną asteroidę: jej wartość bezwzględna oznacza jej rozmiar, a znak — kierunek, dodatni w prawo, a ujemny w lewo.
Gdy asteroida poruszająca się w prawo napotka asteroidę poruszającą się w lewo, zderzają się. Mniejsza eksploduje; jeśli mają ten sam rozmiar, eksplodują obie. Asteroidy poruszające się w tym samym kierunku nigdy się nie spotkają. Zwróć asteroidy, które pozostały po wszystkich zderzeniach, w ich pierwotnej kolejności. Wynik może być pusty.
Funkcja
- asteroidsinteger-array
- asteroidy od lewej do prawej, znak określa kierunek, wartość bezwzględna określa rozmiar
- Zwracainteger-array
- pozostałe asteroidy od lewej do prawej, być może żadne
Ograniczenia
1 ≤ asteroids.length ≤ 104-1000 ≤ asteroids[i] ≤ 1000asteroids[i] ≠ 0
Przykłady
- Wejście
- asteroids = [4, 9, -6, 2, -3]
- Wyjście
- [4, 9]
- Wyjaśnienie
- 9 spotyka -6 i wygrywa. 2 spotyka -3 i eksploduje, a potem -3 leci dalej w stronę 9 i też eksploduje. Nic innego nie porusza się w stronę czegokolwiek, więc pozostają 4 i 9.
- Wejście
- asteroids = [6, -6]
- Wyjście
- []
- Wyjaśnienie
- 6 i -6 zderzają się z taką samą siłą, więc oba wybuchają, a wynik jest pusty.
- Wejście
- asteroids = [-2, -7, 3, 8]
- Wyjście
- [-2, -7, 3, 8]
- Wyjaśnienie
- -2 i -7 lecą w lewo, a 3 i 8 lecą w prawo, więc obie grupy oddalają się od siebie. Nic się nie zderza i wszystkie cztery asteroidy przetrwają.
Pytanie dodatkowe
Stos określa, które asteroidy przetrwają. Jak można również podać dla każdej asteroidy, która eksploduje, indeks asteroidy, która ją zniszczyła?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Do zderzenia potrzebny jest obiekt poruszający się w prawo po lewej stronie i obiekt poruszający się w lewo po prawej stronie. Asteroida poruszająca się w lewo, przed którą nic nie porusza się w prawo, jest już zawsze bezpieczna. Przejdź przez rząd od lewej do prawej: które wcześniejsze asteroidy nowy obiekt poruszający się w lewo może jeszcze uderzyć?
Nowy poruszający się w lewo trafia najpierw w najbliższy ocalały obiekt poruszający się w prawo, potem w następny i tak dalej, aż eksploduje lub zabraknie obiektów poruszających się w prawo. Dotychczasowi ocalali zachowują się jak stos: następny może zostać trafiony tylko najnowszy z nich.
Trzymaj ocalałe obiekty na stosie. Wstawiaj każdy obiekt poruszający się w prawo. Dla obiektu poruszającego się w lewo, dopóki na szczycie stosu znajduje się mniejszy obiekt poruszający się w prawo, zdejmuj go ze stosu. Jeśli na szczycie stosu znajduje się obiekt poruszający się w prawo o tym samym rozmiarze, zdejmij go ze stosu i odrzuć nowy obiekt. Jeśli na szczycie stosu znajduje się większy obiekt, odrzuć nowy obiekt. W przeciwnym razie wstaw go na stos.
Rozwiązanie
Jeden obiekt poruszający się w lewo może zniszczyć długi ciąg obiektów poruszających się w prawo, a każde zderzenie może odsłonić nową parę, która zderzy się jako następna. Nowa asteroida zawsze napotyka najpierw ostatni obiekt, który przetrwał, więc stos ocalałych pozwala rozstrzygnąć każde zderzenie w jednym przebiegu.
Usuwaj awarie pojedynczo
Poprawne, ale nie kończy się na największych testach
Intuicja
Dwie asteroidy zderzają się dokładnie wtedy, gdy asteroida poruszająca się w prawo znajduje się bezpośrednio na lewo od asteroidy poruszającej się w lewo. Znajdź pierwszą taką parę, usuń ją i ponownie przeskanuj wiersz od lewej. Gdy nie zostanie już żadna taka para, nic już nigdy się nie zderzy i wiersz jest odpowiedzią.
Kolejność rozstrzygania nie ma znaczenia: dwie sąsiadujące asteroidy skierowane ku sobie zderzą się ze sobą, zanim którakolwiek z nich zderzy się z czymkolwiek innym.
Każde zderzenie wymaga nowego skanowania i usunięcia elementu ze środka wiersza. Przy 9,999 małych asteroidach poruszających się w prawo, po których następuje -1000, podczas każdego skanowania przechodzisz przez wiersz, by zniszczyć jedną asteroidę poruszającą się w prawo: około 5 × 10^7 kroków.
Algorytm
- Skopiuj wiersz, aby móc usunąć z niego asteroidy.
- Szukaj od lewej pierwszego indeksu
i, dla któregorow[i] > 0irow[i+1] < 0. - Jeśli takiego indeksu nie ma, zwróć wiersz.
- W przeciwnym razie usuń mniejszą z tych dwóch asteroid lub obie, jeśli mają taki sam rozmiar, i szukaj ponownie.
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]Stos ocalałych
Intuicja
Na stosie trzymaj dotychczas ocalałe asteroidy. Nigdy nie ma na nim prawego asteroidu, po którym następuje lewy, ponieważ taka para zdążyłaby już się zderzyć, więc stos zawiera ocalałe lewe asteroidy, a po nich prawe.
Nowy prawy asteroid odlatuje od wszystkich asteroid na stosie, więc dodajesz go na stos. Nowy lewy asteroid leci w stronę prawych asteroid na szczycie i napotyka najpierw tę najnowszą, więc tylko ona może być następnym asteroidą, w którą uderzy. W pierwszym przykładzie -3 zdejmuje 2, a następnie eksploduje po zderzeniu z 9, a stos [4, 9] jest odpowiedzią w swojej pierwotnej kolejności.
Każdy asteroid jest dodawany na stos najwyżej raz i zdejmowany z niego najwyżej raz, więc przejście ma złożoność O(n), nawet jeśli jeden lewy asteroid usuwa długi ciąg.
Algorytm
- Zacznij od pustego stosu ocalałych asteroid.
- Dla każdej asteroidy, jeśli porusza się w prawo, umieść ją na stosie i kontynuuj.
- Jeśli porusza się w lewo, zdejmuj asteroidy poruszające się w prawo ze szczytu stosu, dopóki są od niej mniejsze.
- Jeśli na szczycie znajduje się teraz asteroida poruszająca się w prawo o takim samym rozmiarze, zdejmij ją ze stosu i odrzuć nową asteroidę. Jeśli na szczycie znajduje się większa asteroida poruszająca się w prawo, odrzuć nową asteroidę. W przeciwnym razie umieść ją na stosie.
- Zwróć stos od dołu do góry.
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
Pułapki i przypadki brzegowe
- Traktowanie lewojadącego, za którym jedzie prawojadący, jako zderzenia. W
[-2, -7, 3, 8]grupy oddalają się od siebie i wszystkie cztery obiekty przetrwają. - Używanie
ifzamiastwhileprzy usuwaniu elementów ze stosu. W[1, 2, 3, 4, 5, -15]lewojadący niszczy wszystkie pięć prawojadących i przetrwa. - Pominięcie przypadku równości.
[6, -6]musi usunąć 6 ze stosu i odrzucić -6, pozostawiając pusty wynik. - Dodanie na stos lewojadącego, który przegrał. W
[9, -6]-6 eksploduje i nie może trafić na stos; zachowaj flagę określającą, czy nadal żyje.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu zderzenia asteroid?
O(n) czasu i O(n) pamięci przy użyciu stosu ocalałych, ponieważ każda asteroida jest dodawana i zdejmowana ze stosu najwyżej raz. Ponowne przeszukiwanie wiersza po każdym zderzeniu kosztuje O(n²).
Dlaczego stos jest odpowiednią strukturą danych do rozwiązania problemu kolizji asteroid?
Nowa asteroida może dotrzeć tylko do ocalałych znajdujących się najbliżej niej i napotyka ich w kolejności od najnowszego do najstarszego. To zasada „ostatni wszedł, pierwszy wyszedł”. To, co znajduje się na stosie na końcu, nie może już się zderzyć, więc jest ostatnim wierszem.
Czy problem kolizji asteroid można rozwiązać przy użyciu O(1) dodatkowej pamięci?
Tak, jeśli możesz nadpisać dane wejściowe. Użyj początku tablicy jako stosu: zachowuj indeks zapisu top, porównuj z asteroids[top-1] i zwróć pierwsze top elementów.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def asteroidCollision(asteroids):
# Wpisz tutaj kodTest #1
Test #2
Test #3
Argument
asteroids = [4, 9, -6, 2, -3]
Oczekiwany wynik
[4, 9]