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 条评论
登录 后参与评论

相关文章

来自专栏青玉伏案

窥探Swift之别样的枚举类型

  想必写过程序的童鞋对枚举类型并不陌生吧,使用枚举类型的好处是多多的,在这儿就不做过多的赘述了。Fundation框架和UIKit中的枚举更是数不胜数,枚举可...

1797
来自专栏JackieZheng

初探JavaScript(四)——作用域链和声明提前

前言:最近恰逢毕业季,千千万万的学生党开始步入社会,告别象牙塔似的学校生活。往往在人生的各个拐点的时候,情感丰富,感触颇深,各种对过去的美好的总结,对未来的展望...

1815
来自专栏计算机视觉与深度学习基础

Leetcode 18 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such tha...

1907
来自专栏计算机视觉与深度学习基础

Leetcode 162 Find Peak Element

A peak element is an element that is greater than its neighbors. Given an inpu...

1917
来自专栏三流程序员的挣扎

什么是闭包

闭包 Closures,最初接触大概是在看 Swift 文档的时候,但是似是而非,好像明白了,好像就没彻底明白,记得当时也查了一些资料,终究是没彻底弄清楚。

501
来自专栏趣谈编程

二分查找

面试官:写个二分热热身 我心想:不用热身,热的手已经出汗了 二分查找有着查找速度快,平均性能好等优点,但必须要求待查表为有序表,且插入删除困难,面试比较常考,今...

1916
来自专栏小白客

Python基础学习-简单数据类型

一:字符串 1:.title()方法将每个单词的首字母改为大写 例: ? 输出: ? 2:.upper()方法将字符串全部改为大写 例: ...

3948
来自专栏企鹅号快讯

【编程经验】Python之collections模块

collections模块是一个不用不知道,一用就上瘾的模块。因为它提供了几种非常方便的数据结构和方法,在有些情况下特别好用。今天给大家总结一下其中的Order...

1665
来自专栏程序员宝库

关于 Java 你不知道的 10 件事

作为 Java 书呆子,比起实用技能,我们会对介绍 Java 和 JVM 的概念细节更感兴趣。因此我想推荐 Lukas Eder 在 jooq.org 发表的原...

3496
来自专栏程序员宝库

关于 Java 你不知道的 10 件事

作为 Java 书呆子,比起实用技能,我们会对介绍 Java 和 JVM 的概念细节更感兴趣。因此我想推荐 Lukas Eder 在 jooq.org 发表的原...

2785

扫码关注云+社区