LWC 60:735. Asteroid Collision

LWC 60:735. Asteroid Collision

传送门:735. Asteroid Collision

Problem:

We are given an array asteroids of integers representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed. Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5, 10, -5] Output: [5, 10] Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8, -8] Output: [] Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10, 2, -5] Output: [10] Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Example 4:

Input: asteroids = [-2, -1, 1, 2] Output: [-2, -1, 1, 2] Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.

Note:

The length of asteroids will be at most 10000.

Each asteroid will be a non-zero integer in the range [-1000, 1000].

思路: 问题的归简,相碰的行星一定是→←这个方向,所以当遇到前后两行星属于这种方向时,则缩小规模,如果质量相等则都消失,否则质量较小的消失。采用栈的形式始终维持新鲜的最右位置和加入的行星比较即可。

Java版:

List{Integer} 转 int[] : list.stream().mapToInt(i -> i).toArray();

    public int[] asteroidCollision(int[] asteroids) {
        int n = asteroids.length;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; ++i) {

            if (stack.isEmpty()) {
                stack.push(asteroids[i]);
                continue;
            }

            int prev = stack.peek();
            boolean pf = prev >= 0;

            int curr =  asteroids[i];
            boolean cf = curr >= 0;

            if (pf == true && cf == false) {
                if (Math.abs(prev) > Math.abs(curr)) {

                }
                else if (Math.abs(prev) < Math.abs(curr)) {
                    stack.pop();
                    i = i - 1;
                }
                else {
                    stack.pop();
                }
            }
            else {
                stack.push(curr);
            }
        }

        return stack.stream().mapToInt(i -> i).toArray();
    }

Python 版本:

    def asteroidCollision(self, asteroids):
        """
        :type asteroids: List[int]
        :rtype: List[int]
        """
        stack = []
        i = 0
        n = len(asteroids)
        while i < n:
            if stack == []:
                stack.append(asteroids[i])
                i = i + 1
                continue

            prev = stack[-1]
            curr = asteroids[i]
            if prev >= 0 and curr < 0:
                if abs(prev) > abs(curr):
                    pass
                elif abs(prev) < abs(curr):
                    stack.pop()
                    i = i - 1
                else:
                    stack.pop()
            else:
                stack.append(curr)
            i = i + 1
        return stack

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Phoenix的Android之旅

如何用反射突破private方法的限制

反射作为Java的一个提高点,经常作为面试的内容之一。今天介绍一下最基本的反射的使用。 如何用反射来使用Class中的private方法。

892
来自专栏程序员互动联盟

【编程基础】Java的接口和抽象类

对于面向对象编程来说,抽象是它的一大特征之一。在Java中,可以通过两种形式来体现OOP的抽象:接口和抽象类。这两者有太多相似的地方,又有太多不同的地方。很多人...

2867
来自专栏Java面试通关手册

最最最常见的Java面试题总结-第一周

这里会分享一些出现频率极其极其高的面试题,初定周更一篇,什么时候更完什么时候停止。

701
来自专栏noteless

正确重写hashcode hashcode与equals方法 集合元素如何判断是否相等 集合如何查看是否包含某个元素

相等的两个对象,即equals(Object)方法判断两个对象相等,那么他们必须要有相同的hashcode

1251
来自专栏Java帮帮-微信公众号-技术文章全总结

09(02)总结final,多态,抽象类,接口

(4)抽象类的练习 A:猫狗案例练习 B:老师案例练习 C:学生案例练习 D:员工案例练习 /* A: 猫狗案例 具体事物:猫,狗 共性:姓名,...

4026
来自专栏大神带我来搬砖

编写高质量的代码——详解Builder模式

假设有一个用有多个属性的java bean,想在得到这个bean的时候,就已经将其属性初始化好 public class Persion { priv...

2716
来自专栏Java帮帮-微信公众号-技术文章全总结

第十一天 面向对象-接口多态【悟空教程】

1404
来自专栏技术与生活

Lambda 深入浅出

非常简单,那么问题来了,如果这个时候需求变动,要求选择的是红色的并且重量大于10的,那么怎么办。小 case,不就一行代码的事

992
来自专栏个人随笔

Java 接口理论篇

接口的两层含义:接口作为数据类型   狭义的接口  接口的第二层含义:工具 广义的接口 在接口中所有的变量都是静态常量 在接口中所有方法都是抽象方法 定义一个接...

3236
来自专栏苦逼的码农

从0打卡leetcode之day8--反转整数

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

1234

扫码关注云+社区