首页 文章详情

LeetCode | 735. 行星碰撞

码农UP2U | 213 2021-04-27 04:18 0 0 0
UniSMS (合一短信)


题目描述

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


good-icon 0
favorite-icon 0
收藏
回复数量: 0
    暂无评论~~
    Ctrl+Enter