Столкновение астероидов

Средняя
medium , array , stack
11 December 2023

Описание задачи #

Напишите функцию, которая будет рассчитывать результаты столкновения астероидов.

Входные данные

Массив целых ненулевых чисел. Каждое число обозначает массу астероида, знак — направление движения.

Выходные данные

Массив целых ненулевых чисел. Массив будет описывать множество астероидов, их массу и направление, после того как все астероиды, которые могут столкнуться, столкнутся.

Все астероиды движутся с одинаковой скоростью. Таким образом, астероиды, летящие в одном направлении никогда не столкнутся друг с другом.

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

Ограничения #

Примеры #

  • Входные данные: [5,10,-5]

    Ответ: [5,10]

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

  • Входные данные: [8,-8]

    Ответ: []

    Пояснение: Астероиды движутся навстречу друг другу и имеют одинаковую массу. В результате оба астероида будут уничтожены.

  • Входные данные: [10,2,-5]

    Ответ: [10]

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

Решение через два указателя #

Одно из возможных решений - использовать два указателя. В качестве первых точек выбираем первые два астероида. Действуем по следующему принципу:

  • package main

func asteroidCollisionTwoIdx(asteroids []int) []int {
	i, j := 0, 1

	for i >= 0 && j < len(asteroids) {
		first := asteroids[i]
		second := asteroids[j]

		if first*second > 0 || first < 0 {
			i++
			j++
			continue
		}

		if first > -1*second {
			asteroids = append(asteroids[:i+1], asteroids[j+1:]...)
			continue
		}

		if first < -1*second {
			asteroids = append(asteroids[:i], asteroids[j:]...)
			j--
			i--
			if i < 0 {
				i = 0
				j = 1
			}

			continue
		}

		if first == -1*second {
			asteroids = append(asteroids[:i], asteroids[j+1:]...)
			j--
			i--
			if i < 0 {
				i = 0
				j = 1
			}
			continue
		}
	}

	return asteroids
}

  • export const asteroidCollisionTwoIdx = (asteroids: number[]): number[] => {
    let i = 0;
    let j = 1;

    while (i >= 0 && j < asteroids.length) {
        const first = asteroids[i]
        const second = asteroids[j]

        if (first * second > 0 || first < 0) {
            i++
            j++
            continue
        }

        if (first > -1 * second) {
            asteroids = [...asteroids.slice(0, i + 1), ...asteroids.slice(j + 1)]
            continue
        }

        if (first < -1 * second) {
            asteroids = [...asteroids.slice(0, i), ...asteroids.slice(j)]
            j--
            i--
            if (i < 0) {
                i = 0
                j = 1
            }

            continue
        }

        if (first == -1 * second) {
            asteroids = [...asteroids.slice(0, i), ...asteroids.slice(j + 1)]
            j--
            i--
            if (i < 0) {
                i = 0
                j = 1
            }
        }
    }

    return asteroids
}

Оценка сложности #

По времени

Сложность O(n2), где n — длина строки.

Несмотря на то, что мы работали с двумя указателями и не запускали внутренних циклов, стоит вспомнить, что операция вырезания элемента из середины массива оценивается как O(n) (так как весь «хвост» массива нужно сдвинуть на один элемент влево).

По памяти

Сложность O(1), так как все изменения мы делали in-place, без выделения доп памяти.

Решение через стек #

Задачу можно решить за линейное время с использованием структуры данных стек.

Основная идея решения мало чем отличается от задачи по валидации скобочной последовательности, которую мы разбирали ранее.

Для решения задачи, нам необходимо завести стек (можно реализовать стек через массив) и в цикле перебрать элементы исходного массива:

Для простоты мы реализовали этот подход через рекурсивную функцию appendAsteroidToStack, но, можно обойтись и без рекурсии.

  • package main

func asteroidCollision(asteroids []int) []int {
	stack := make([]int, 0, len(asteroids))

	for i := 0; i < len(asteroids); i++ {
		stack = appendAsteroidToStack(stack, asteroids[i])
	}

	return stack
}

func appendAsteroidToStack(stack []int, asteroid int) []int {
	if len(stack) == 0 {
		return append(stack, asteroid)
	}

	current := stack[len(stack)-1]

	if current*asteroid > 0 || current < 0 {
		return append(stack, asteroid)
	}

	if current > -1*asteroid {
		return stack
	}

	if current < -1*asteroid {
		return appendAsteroidToStack(stack[:len(stack)-1], asteroid)
	}

	return stack[:len(stack)-1]
}

  • export function asteroidCollision(asteroids: number[]): number[] {
    let stack: number[] = []

    asteroids.forEach((asteroid) => {
        stack = appendAsteroidToStack(stack, asteroid)
    })

    return stack
}

function appendAsteroidToStack(stack: number[], asteroid: number): number[] {
    if (stack.length == 0) {
        stack.push(asteroid)
        return stack
    }

    const current = stack[stack.length - 1]

    if (current * asteroid > 0 || current < 0) {
        stack.push(asteroid)
        return stack
    }

    if (current > -1 * asteroid) {
        return stack
    }

    if (current < -1 * asteroid) {
        stack.pop()
        return appendAsteroidToStack(stack, asteroid)
    }

    stack.pop()

    return stack
}

Оценка сложности #

По времени

Сложность O(n), где n — длина строки.

В худшем случае нам придется положить n-1 элементов в стек, а после извлечь все элементы. То есть, максимальная сложность равна 2n, что с точки зрения оценки алгоритма эквивалентно O(n).

По памяти

Сложность O(n), так как нам пришлось создать стек для хранения данных.

Оригинал задачи на Leetcode
< Предыдущая задача
Следующая задача >