专栏首页码农UP2ULeetCode | 735. 行星碰撞

LeetCode | 735. 行星碰撞

题目描述

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

本文分享自微信公众号 - 码农UP2U(gh_3c91b47a82e0),作者:码农UP2U

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 735. 行星碰撞(栈)

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

    Michael阿明
  • Leetcode | 第6节:栈与队列

    大家好!这一节我们介绍一些栈与队列相关的问题。这一些问题多半都有一些技巧(比方说时常使用的单调栈等),但也不是完全没有套路。

    学弱猹
  • LWC 60:735. Asteroid Collision

    LWC 60:735. Asteroid Collision 传送门:735. Asteroid Collision Problem: We are give...

    用户1147447
  • 手把手教你用Python改造一款外星人入侵小游戏

    很多朋友都是从python编程:从入门到实践开始的python学习,这本书还是比较适合初学者的。

    Python进阶者
  • python应用篇之外星人入侵项目——外星人(完)

    上篇文章给大家介绍的是让外星人动起来,包括左右移动,以及当遇到屏幕边缘的时候让其向下移动。本文给大家介绍用我们的飞船射杀外星人功能的实现。

    一计之长
  • python应用篇之外星人入侵项目——外星人(完结)

      我们上篇文章给大家介绍了射杀外星人功能的实现,其中主要包括检测子弹与外星人碰撞,生成新的外星人群、提高子弹的速度以及最后将update_bullets()方...

    一计之长
  • 碰撞和掩码 第2部分-生成不可预测的事件

    在上一节中,我们通过触摸陷阱使我们的玩家死亡。通过练习,任何人都可以跳过静态陷阱并完美运行。出于这个原因,大多数游戏围绕着随机事件。在我们的游戏中,我们将通过向...

    iOSDevLog
  • 挑战程序竞赛系列(22):3.2弹性碰撞

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 如何利用机器人清理太空垃圾?

    尽管我们不太关注,但是越来越多的人在日常生活中需要依赖这些在太空的卫星,像地球观测卫星,通信卫星和全球定位系统等等。轨道碎片不仅仅威胁太空的开发和探测,同样也威...

    机器人网
  • unity官方案例精讲(第三章)--星际航行游戏Space Shooter

    导入的工程包中,包含着一个完整的 _scene---Main场景,创建一个全新场景,会在其中实现大部分功能

    酱紫安
  • ASCII码模拟星系碰撞:牛顿引力定律融合C++的「奇迹」

    https://www.youtube.com/watch?v=DMOK5BS6KJw

    新智元
  • 区块链基础之哈希函数

    hash函数的作用hash算法的安全性 常见的Hash算法 MD5 SHA1 SHA256 哈希碰撞钱包的...

    efonfighting
  • 最便宜的那款特斯拉,刚刚喜提“最安全汽车”称号(然后被打脸)

    昨天,特斯拉官网表示,在NHTSA(美国国家公路交通安全局)新出炉的安全测评中,特斯拉迎来人生春天:

    量子位
  • 学习 Phaser.js HTML5游戏开发-DAY1

    Github: https://github.com/photonstorm/phaser

    tonglei0429
  • Flutter第2天--Animation动画+粒子运动

    张风捷特烈
  • 为何你的弹球如丝般顺滑?不停歇的球!技术分享!源码相送!

    最近有小伙伴玩了【不停歇的球】,问我怎么做到这个流畅度的?于是,我稍做整理,把开发中的一些点提炼出来,有了这篇文章!

    白玉无冰
  • 计算机网络学习--数据链路层

    第一章 概述 第二章 物理层 第三章 数据链路层 第四章 网络层 第五章 传输层 第六章 应用层

    shimeath
  • 什么是区块链技术?

    区块链是一种分类帐,它使用加密技术和激励措施并以防篡改的方式记录交易。这使匿名双方进行信任最小化(trust-minimized)交易,而不需要可信中介。

    用户2357564
  • 野路子搞算法 · 让算法可视化《leetcode03.无重复字符的最长子串》

    在刷了第一道 leetcode 的题以后我一直在思考,怎么才能让小白更清楚的了解到整个算法运行的过程。如果只是单纯的一点点看代码,从中摸清楚整个流程确实还是有一...

    小傅哥

扫码关注云+社区

领取腾讯云代金券