当前位置： 面试刷题>> 小行星的碰撞 (经典算法题500道)

题目描述补充

题目：小行星的碰撞

给定一个整数数组 asteroids，其中 asteroids[i] 表示第 i 颗小行星的位置（位置值越小，小行星越靠近左侧）。小行星以给定的顺序从左向右移动。

当两颗小行星发生碰撞时，体积较小的小行星会被完全摧毁，而体积较大的小行星会保持其原有方向继续移动。如果两颗小行星的体积相同，则它们都会被摧毁。

编写一个函数，该函数接受一个整数数组 asteroids 作为输入，并返回碰撞后剩余的小行星的数组。

示例

输入：asteroids = [5, 10, -5]

输出：[5, 10]

解释：第二颗小行星与第三颗小行星发生碰撞，第三颗小行星被摧毁，因此只剩下第一颗和第二颗小行星。

示例代码

PHP 示例

function asteroidCollision($asteroids) {
    $stack = [];
    foreach ($asteroids as $asteroid) {
        if ($asteroid > 0) {
            // 如果是正向小行星，直接入栈
            $stack[] = $asteroid;
        } else {
            // 如果是负向小行星
            while (!empty($stack) && end($stack) > 0 && $stack[count($stack) - 1] < abs($asteroid)) {
                // 栈顶为正向且小于负向小行星，弹出栈顶
                array_pop($stack);
            }
            if (!empty($stack) && end($stack) == abs($asteroid)) {
                // 栈顶为正向且等于负向小行星，两者都弹出
                array_pop($stack);
            } elseif (!empty($stack) && end($stack) > 0) {
                // 栈顶为正向且大于负向小行星，负向小行星被摧毁
                continue;
            } else {
                // 栈为空或栈顶为负向，负向小行星入栈
                $stack[] = $asteroid;
            }
        }
    }
    return $stack;
}

// 测试用例
$asteroids = [5, 10, -5];
$result = asteroidCollision($asteroids);
print_r($result); // 输出: Array ( [0] => 5 [1] => 10 )

Python 示例

def asteroidCollision(asteroids):
    stack = []
    for asteroid in asteroids:
        if asteroid > 0:
            stack.append(asteroid)
        else:
            while stack and stack[-1] > 0 and stack[-1] < abs(asteroid):
                stack.pop()
            if stack and stack[-1] == abs(asteroid):
                stack.pop()
            elif not stack or (stack and stack[-1] < 0):
                stack.append(asteroid)
    return stack

# 测试用例
asteroids = [5, 10, -5]
result = asteroidCollision(asteroids)
print(result)  # 输出: [5, 10]

JavaScript 示例

function asteroidCollision(asteroids) {
    let stack = [];
    for (let asteroid of asteroids) {
        if (asteroid > 0) {
            // 如果是正向小行星，直接入栈
            stack.push(asteroid);
        } else {
            // 如果是负向小行星
            while (stack.length > 0 && stack[stack.length - 1] > 0 && stack[stack.length - 1] < Math.abs(asteroid)) {
                // 栈顶为正向且小于负向小行星，弹出栈顶
                stack.pop();
            }
            if (stack.length > 0 && stack[stack.length - 1] === Math.abs(asteroid)) {
                // 栈顶为正向且等于负向小行星，两者都弹出
                stack.pop();
            } else if (stack.length > 0 && stack[stack.length - 1] > 0) {
                // 栈顶为正向且大于负向小行星，负向小行星被摧毁
                continue;
            } else {
                // 栈为空或栈顶为负向，负向小行星入栈
                stack.push(asteroid);
            }
        }
    }
    return stack;
}

// 测试用例
let asteroids = [5, 10, -5];
let result = asteroidCollision(asteroids);
console.log(result); // 输出: [5, 10]

码小课相关内容

码小课网站中涵盖了更多算法和数据结构的深入解析与实战案例，包括但不限于排序算法、搜索算法、图论、动态规划等经典问题，以及更多面试高频题目的详细解答和代码实现，非常适合广大编程爱好者和准备面试的开发者学习。

推荐面试题