「每日LeetCode」2022年7月13日

本文最后更新于：2023年3月19日 晚上

735.行星碰撞

735.行星碰撞

Category Difficulty Likes Dislikes
algorithms Medium (41.33%) 293 -

Tags
Companies
给定一个整数数组 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

Discussion | Solution

思路

暴力模拟，遍历数组，只有两者方向一致的时候才取绝对值，比较大小，删除较小的那个，相同时两个都删除。遍历之后判断当前数组是否是左边都是负数，右边都是正数的形式，不是的话再进行上面的操作。

解答

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
 * @lc app=leetcode.cn id=735 lang=javascript
 *
 * [735] 行星碰撞
 */

// @lc code=start
/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function (asteroids) {
  const action = () => {
    for (let i = 0; i < asteroids.length - 1; i++) {
      const cur = asteroids[i];
      const next = asteroids[i + 1];

      if (
        (cur > 0 && next > 0) ||
        (cur < 0 && next < 0) ||
        (cur < 0 && next > 0)
      )
        continue;

      const num1 = Math.abs(cur),
        num2 = Math.abs(next);

      if (num1 > num2) {
        asteroids.splice(i + 1, 1);
      } else if (num1 < num2) {
        asteroids.splice(i, 1);
      } else {
        asteroids.splice(i, 2);
      }
    }
  };

  const check = () => {
    let flag = asteroids[0] < 0;
    for (const item of asteroids) {
      if (item > 0) {
        flag = false;
        continue;
      }

      if (!flag && item < 0) {
        return false;
      }
    }
    return true;
  };

  action();

  while (asteroids.length) {
    if (check()) {
      break;
    } else {
      action();
    }
  }

  return asteroids;
};
// @lc code=end