Asteroid Collision

Q: Какова временная сложность задачи «Столкновение астероидов»?

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

Q: Почему стек — подходящая структура данных для задачи о столкновении астероидов?

Новый астероид может достичь только ближайших к нему выживших, и сталкивается с ними от самых новых к самым старым. Это принцип «последним пришёл — первым вышел». То, что останется в стеке в конце, уже не может столкнуться, поэтому это итоговый ряд.

Q: Можно ли решить задачу «Столкновение астероидов» с дополнительной памятью O(1)?

Да, если можно перезаписать входной массив. Используйте начало массива как стек: храните индекс записи top , сравнивайте с asteroids[top-1] и возвращайте первые top элементов.

СреднеСтек

+10

Ряд астероидов движется вдоль линии с одинаковой скоростью. Каждое значение в asteroids описывает один астероид: его абсолютное значение — это его размер, а знак указывает направление: положительный — вправо, отрицательный — влево.

Когда астероид, движущийся вправо, встречается с астероидом, движущимся влево, они сталкиваются. Меньший взрывается; если они одинакового размера, взрываются оба. Астероиды, движущиеся в одном направлении, никогда не встречаются. Верни астероиды, которые остались после всех столкновений, в исходном порядке. Результат может быть пустым.

Функция

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

asteroidsinteger-array: астероиды слева направо, знак для направления, абсолютное значение для размера
Возвращаетinteger-array: оставшиеся астероиды слева направо, возможно, ни одного

Ограничения

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

Примеры

Ввод: asteroids = [4, 9, -6, 2, -3]
Вывод: [4, 9]
Пояснение: 9 встречает -6 и побеждает. 2 встречает -3 и взрывается, а затем -3 летит дальше к 9 и тоже взрывается. Больше ничто ни к чему не движется, поэтому остаются 4 и 9.

Дополнительный вопрос

Стек определяет, какие астероиды выживут. Как дополнительно сообщать для каждого взорвавшегося астероида индекс астероида, который его уничтожил?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Один астероид, движущийся влево, может уничтожить длинную цепочку астероидов, движущихся вправо, а каждое столкновение может открыть новую пару, которая столкнётся следующей. Новый астероид всегда первым встречает последнего выжившего, поэтому стек выживших позволяет разрешить все столкновения за один проход.

Устраняйте сбои по одному

Верно, но не успевает на самых больших тестах

Идея

Два астероида сталкиваются, только когда астероид, движущийся вправо, находится непосредственно слева от астероида, движущегося влево. Найди первую такую пару, разреши столкновение и снова просканируй ряд слева направо. Когда таких пар не останется, столкновений больше никогда не будет, и ответом станет этот ряд.

Порядок разрешения столкновений не имеет значения: две соседние астероиды, направленные друг к другу, столкнутся раньше, чем любая из них сможет столкнуться с чем-либо ещё.

Каждое столкновение требует нового сканирования и удаления астероида из середины ряда. Если за 9,999 небольшими астероидами, движущимися вправо, следует -1000, при каждом сканировании приходится проходить по ряду, чтобы уничтожить один астероид, движущийся вправо: около 5 × 10^7 шагов.

Алгоритм

Скопируй строку, чтобы удалить из неё астероиды.
Просматривай строку слева направо, пока не найдёшь первый индекс i, для которого row[i] > 0 и row[i+1] < 0.
Если такого индекса нет, верни строку.
В противном случае удали меньший из двух астероидов или оба, если их размеры равны, и начни сканирование заново.

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]

Стопка выживших

Идея

Пока что храните выжившие астероиды в стеке. В нём никогда не бывает правого астероида, за которым следует левый: такая пара уже столкнулась бы, поэтому в стеке сначала идут уцелевшие левые астероиды, а за ними — правые.

Новый правый астероид улетает от всех астероидов в стеке, поэтому добавьте его в стек. Новый левый астероид летит навстречу правым астероидам сверху и встречает сначала самый новый, поэтому следующим он может столкнуться только с верхним астероидом. В первом примере -3 выталкивает 2, затем взрывается при столкновении с 9, и стек [4, 9] — это ответ в исходном порядке.

Каждый астероид добавляется в стек не более одного раза и удаляется из него не более одного раза, поэтому проход занимает O(n), даже если один левый астероид уничтожает длинную последовательность.

Алгоритм

Начните с пустого стека выживших астероидов.
Для каждого астероида: если он движется вправо, поместите его в стек и продолжайте.
Если он движется влево, извлекайте с вершины движущиеся вправо астероиды, пока они меньше него.
Если теперь на вершине находится астероид того же размера, движущийся вправо, извлеките его и отбросьте новый астероид. Если на вершине находится более крупный астероид, движущийся вправо, отбросьте новый астероид. В противном случае поместите его в стек.
Верните стек снизу вверх.

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

Ловушки и крайние случаи

Считать, что левый объект, за которым следует правый объект, приводит к столкновению. В [-2, -7, 3, 8] группы разлетаются в разные стороны, и все четыре объекта выживают.
Использовать if вместо while для извлечения элементов. В [1, 2, 3, 4, 5, -15] левый объект уничтожает все пять правых объектов и выживает.
Не учитывать случай равенства. Для [6, -6] нужно извлечь 6 и отбросить -6, чтобы результат оказался пустым.
Добавлять в стек проигравший левый объект. В [9, -6] объект -6 взрывается и не должен попасть в стек; используйте флаг, указывающий, остался ли он цел.

Частые вопросы3

Какова временная сложность задачи «Столкновение астероидов»?

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

Почему стек — подходящая структура данных для задачи о столкновении астероидов?

Новый астероид может достичь только ближайших к нему выживших, и сталкивается с ними от самых новых к самым старым. Это принцип «последним пришёл — первым вышел». То, что останется в стеке в конце, уже не может столкнуться, поэтому это итоговый ряд.

Можно ли решить задачу «Столкновение астероидов» с дополнительной памятью O(1)?

Да, если можно перезаписать входной массив. Используйте начало массива как стек: храните индекс записи top, сравнивайте с asteroids[top-1] и возвращайте первые top элементов.

def asteroidCollision(asteroids):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

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

Ожидаемый вывод

[4, 9]