小鲸鱼的梦境
0%

『LeetCode』735 行星碰撞

发表于 分类于 Valine：
本文字数： 3.9k 阅读时长 ≈ 4 分钟

题目

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 <= 10^{4}\)
  • \(-1000 <= asteroids[i] <= 1000\)
  • \(asteroids[i] != 0\)

标签

栈, 数组

相似题目

题解

【行星碰撞】模拟模拟

简单模拟

最简单的思路就是循环的两两检查是否会碰撞，对碰撞的星球进行处理直到没有碰撞发生为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Code language: Python
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        while True:
            n = len(asteroids)
            nxt = list()
            p = False
            for i, j in zip(range(n - 1), range(1, n)):
                if asteroids[i] > 0 and asteroids[j] < 0:
                    a, b = map((lambda x: abs(asteroids[x])), (i, j))
                    if a < b:
                        asteroids[i] = 0
                    elif a > b:
                        asteroids[j] = 0
                    else:
                        asteroids[i], asteroids[j] = 0, 0
                    p = True
                if asteroids[i] != 0:
                    nxt.append(asteroids[i])
            if asteroids and asteroids[-1] != 0:
                nxt.append(asteroids[-1])
            asteroids = nxt
            if not p:
                break
        return asteroids
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/** Code language: JavaScript
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function(asteroids) {
    while (true) {
        let n = asteroids.length - 1;
        var nxt = new Array();
        p = false;
        for (let i = 0; i < n; ++i) {
            if (asteroids[i] > 0 && asteroids[i + 1] < 0) {
                let cur = asteroids[i] + asteroids[i + 1];
                if (cur > 0) asteroids[i + 1] = 0;
                else if (cur < 0) asteroids[i] = 0;
                else {
                    asteroids[i] = 0;
                    asteroids[i + 1] = 0;
                }
                p = true;
            }
            if (asteroids[i] != 0) nxt.push(asteroids[i]);
        }
        if (n >= 0 && asteroids[n] != 0) nxt.push(asteroids[n]);
        asteroids = nxt;
        if (!p) break;
    }
    return asteroids;
};
  • 时间复杂度: \(O(n^2)\), 最坏情况下有 1 颗星球把其他 \(n - 1\) 颗星球都撞爆炸了，循环会执行 \(n\) 次
  • 空间复杂度: \(O(n)\)

队列

注意到一个星球不会爆炸的其前进方向没有比它大(暂时忽略一样大的情况)的星球，这包含了两种可能：

  1. 前进方向上没有比它大的星球
  2. 前进方向的前面有一个更大的同方向的星球把前面比它大的星球都撞爆炸了，即前面比它大的星球为其清理干净了道路

那么我们可以以一种便捷的方法进行模拟，即维护一个队列作为星球队列，我们从左向右扫描所有星球，有以下几种情况：

  • 队尾星球正向，新来的星球也是正向的，那么加入队尾
  • 队尾星球负向，新来的星球也是负向的，那么加入队尾
  • 队尾星球正向，新来的星球负向，那么新来的星球会与队尾星球发生碰撞，若队尾星球爆炸了，那么还会与队列中剩下的反方向星球碰撞直到队列中剩下星球与其方向相同或队列为空或者新来的星球爆炸了
  • 队尾星球反向，新来的星球正向，两者相互远离，不会碰撞，直接加入队尾

总结起来：只有队尾星球正向，新来的星球负向这一种情况会碰撞。

当扫描完所有星球以后，队列中剩下的星球就是幸存者星球了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Code language: Python
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        st = deque()
        for a in asteroids:
            while st and st[-1] > 0 and a < 0:
                cur = st[-1]
                if cur + a > 0:
                    a = 0
                elif cur + a == 0:
                    st.pop()
                    a = 0
                else:
                    st.pop()
            if a != 0:
                st.append(a)
        return list(st)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Code language: Java
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> st = new ArrayDeque<>();
        for (int a: asteroids) {
            while (!st.isEmpty() && st.peekLast() > 0 && a < 0) {
                int cur = st.peekLast() + a;
                if (cur > 0) a = 0;
                else if (cur == 0) {
                    a = 0; st.pollLast();
                }
                else
                    st.pollLast();
            }
            if (a != 0)
                st.addLast(a);
        }
        int n = st.size();
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) ans[i] = st.poll();
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Code language: C++
class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> st;
        for (int a: asteroids) {
            while (!st.empty() && st.back() > 0 && a < 0) {
                int cur = st.back() + a;
                if (cur > 0) a = 0;
                else if (cur == 0) {
                    a = 0;
                    st.pop_back();
                }
                else st.pop_back();
            }
            if (a != 0) st.push_back(a);
        }
        return st;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/** Code language: JavaScript
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function(asteroids) {
    const st = Array();
    for (let a of asteroids) {
        while (st.length > 0 && st[st.length - 1] > 0 && a < 0) {
            let cur = st[st.length - 1] + a;
            if (cur > 0) a = 0;
            else if (cur == 0) {
                a = 0;
                st.pop();
            }
            else st.pop();
        }
        if (a != 0) st.push(a);
    }
    return st;
};
  • 时间复杂度: \(O(n)\)
  • 空间复杂度: \(O(n)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~