Сложность: medium
Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример:
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true
👨💻 Алгоритм:
1⃣Используйте стек для отслеживания движущихся вправо астероидов.
2⃣Пройдите по массиву астероидов: Если астероид движется вправо, добавьте его в стек. Если астероид движется влево, сравните его с последним астероидом в стеке (если он есть и движется вправо): Если движущийся вправо астероид больше, текущий взорвется. Если движущийся влево астероид больше, последний астероид в стеке взорвется, и продолжите сравнение. Если они одинакового размера, оба взорвутся.
3⃣Добавьте оставшиеся астероиды из стека и текущий астероид в результат.
😎 Решение:
def asteroidCollision(asteroids):
stack = []
for asteroid in asteroids:
while stack and asteroid < 0 < stack[-1]:
if stack[-1] < -asteroid:
stack.pop()
continue
elif stack[-1] == -asteroid:
stack.pop()
break
else:
stack.append(asteroid)
return stack
Ставь 👍 и забирай 📚 Базу знаний