Leetcode75 735小行星碰撞

735小行星碰撞

给定一个整数数组 asteroids，表示在同一行的小行星。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：

输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：

输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

提示：

• 2 <= asteroids.length <= 104
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

Solution 1

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        List<Integer> result = new ArrayList<>();
        for (int asteroid : asteroids) {
            result.add(asteroid);
            while (canCollision(result)) {
                doCollision(result);
            }
        }
        int[] r = new int[result.size()];
        for (int i = 0; i < r.length; i++) {
            r[i] = result.get(i);
        }
        return r;
    }

    boolean canCollision(List<Integer> asteroids) {
        if (asteroids.size() <= 1) {
            return false;
        }
        int length = asteroids.size();
        if (asteroids.get(length - 1) > 0) {
            return false;
        }
        if (asteroids.get(length - 2) < 0) {
            return false;
        }
        // asteroids[-2] > 0 < asteroids[-1]
        return true;
    }

    void doCollision(List<Integer> asteroids) {
        int length = asteroids.size();
        int asteroidASize = asteroids.get(length - 2);
        int asteroidBSize = -asteroids.get(length - 1);
        if (asteroidASize < asteroidBSize) {
            asteroids.remove(length - 2);
        }
        if (asteroidASize == asteroidBSize) {
            asteroids.remove(length - 1);
            asteroids.remove(length - 2);
        }
        if (asteroidASize > asteroidBSize) {
            asteroids.remove(length - 1);
        }
    }
}

Solution 2

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        result = []
        for asteroid in asteroids:
            if len(result) == 0:
                result.append(asteroid)
                continue
            if asteroid > 0:
                result.append(asteroid)
                continue
            # asteroid < 0:
            temp = result[-1]
            if temp < 0:
                result.append(asteroid)
                continue
            # temp > 0 and asteroid < 0:
            asteroidSize = -asteroid
            while True:
                if asteroidSize < temp:
                    break
                if asteroidSize == temp:
                    result.pop()
                    break
                if asteroidSize > temp:
                    result.pop()
                    if len(result) == 0:
                        result.append(asteroid)
                        break
                    else:
                        temp = result[-1]
                        if temp < 0:
                            result.append(asteroid)
                            break
        return result