LeetCode | 735. 行星碰撞

原创码农UP2U 码农日常

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

题目是一道有方向的比大小的问题。且是一道循环消除的问题。题目中给出了 4 组测试用例，也基本上把本题的所有可能的情况都覆盖了。这道题看似使用数组即可完成，但是它有循环消除的情况在里面，因此用栈来做更为方便。

本题我使用 Java 语言来完成，LeetCode 给出的 Java 定义如下：

class Solution {    public int[] asteroidCollision(int[] asteroids) {
    }}

题目分析

题目中说明会给出一个数组，数组中的元素的绝对值是该星球的大小，这里需要注意是绝对值，而不是数值本身。星球有移动的方向，正数表示向右移动，负数表示向左移动。这是基本的情况。

碰撞的规则是，两个星球相遇，则小的会爆炸；如果两个星球相同大小，则都会爆炸。如果两个星球同方向则不会碰撞。

具体来举例看看。

我们使用题目中给出的第三个测试用例，[10, 2, -5] 来进行演示。初始化时如下图。

第一个数值 10，按照题目中给出的，它是向右移动，且栈中为空，那么 10 直接进栈，如下图。

接着第二个数值是 2，同样数值 2 是向右移动，虽然栈中不为空，但是 2 和栈顶的 10 是相同方向的，不会产生碰撞，那么 2 进入栈顶，如下图。

接着下一个数值为 -5，按照题目它是向左侧移动的，它和栈顶的 2 会相撞，因为 2 是向右移动，-5 是向左移动。它们相撞时，因为 -5 的绝对值大于 2，那么 2 则会爆炸，将其出栈，如下图。

此时，-5 需要再次和栈顶的 10 进行相遇，同样狭路相逢数值小的挂，那么 -5 炸了。由于数组中在 -5 后面没有数值，那么整个数组只剩 [10] 了。

通过我们的模拟，得到的结果与题目中给出的测试用例是相同的。

代码实现

看一下我写的 Java 代码，代码如下。

class Solution {    public int[] asteroidCollision(int[] asteroids) {        // 长度小于等于1个，直接返回        // 没有碰撞的机会        final int number = asteroids.length;        if (number <= 1) {            return asteroids;        }
        // 左移和右移        final int left = 0;        final int right = 1;
        Stack<Integer> t = new Stack();                for (int i = 0; i < number; i ++) {            // 当前星球往哪边移动            final int curDirection = asteroids[i] >= 0 ? right : left;            // 当前星球的大小            final int curSize = Math.abs(asteroids[i]);
            // 是否炸了            boolean boom = false;
            while (!t.empty()  // 栈不为空                && (t.peek() >= 0 ? right : left) == right // 栈顶星球是否向右                && curDirection == left) {                 // 当前星球是否香左
                // 相同就碰撞，且栈顶的也出栈                if (t.peek() == curSize) {                    boom = true;                    t.pop();                    break;                }                                // 栈顶的比当前的星球大，则当前星球被撞                // 且跳出循环                if (t.peek() > curSize) {                    boom = true;                    break;                }
                // 上面两个条件都不满足                // 则说明当前的比栈顶的星球大                // 栈顶的星球出栈                t.pop();            }                        // 如果当前的星球没炸            // 则进入栈顶            if (!boom) {                t.push(asteroids[i]);            }        }
        // 通过栈来构造剩下星球的数组        int[] arr = new int[t.size()];        for (int i = t.size() - 1;i >= 0; i --) {            arr[i] = t.peek();            t.pop();        }                return arr;    }}

解释一下代码。

1、如果 asteroids 的长度小于等于 1，那么就说明没有相撞的可能性，直接返回；

2、依次遍历数组，在满足 栈顶元素向右移动且当前元素向左移动 时，用当前的值来循环和栈中的数值进行比对；

3、比较时，大的留下，小的爆炸，也就是大的要进栈；如果相等则同时爆炸；

4、将栈中留下的元素出栈，并放入一个数组中，进行返回。

提交结果

在写完 asteroidCollision 方法体后，点击右下角的 “执行代码”，然后观察 “输出” 和 “预期结果” 是否一致，一致的话就点击 “提交” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，如果没有通过，会给出失败的那一组测试用例，我们继续修改代码。

继续滑动看下一个