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

相关文章

来自专栏算法修养

HOJ 2226&POJ2688 Cleaning Robot(BFS+TSP(状态压缩DP))

Cleaning Robot Time Limit: 1000MS Memory Limit: 65536K Total Submission...

2624
来自专栏机器学习入门

LWC 51:682. Baseball Game

LWC 51:682. Baseball Game 传送门:682. Baseball Game Problem: You’re now a baseball...

1878
来自专栏小樱的经验随笔

HDU 2289 Cup【高精度,二分】

Cup Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

2345
来自专栏我和未来有约会

不规则图形的碰撞检测

public static class CheckHit { public static bool CheckCollision(FrameworkEl...

16910
来自专栏算法修养

Code Forces 149DColoring Brackets(区间DP)

 Coloring Brackets time limit per test 2 seconds memory limit per test 256...

2876
来自专栏算法修养

HDU 1885 Key Task(BFS)

Key Task Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

3294
来自专栏更流畅、简洁的软件开发方式

联动设置

653
来自专栏C/C++基础

C#GDI画立体渐变圆角panel

 private void panel1_Paint(object sender, PaintEventArgs e)         {

581
来自专栏小樱的经验随笔

Codeforces 834E The Bakery【枚举+数位dp】

E. Ever-Hungry Krakozyabra time limit per test:1 second memory limit per test:25...

2758
来自专栏数据和云

高手过招:用SQL解决环环相扣的刑侦推理问题(苏旭辉版本)

本文是继 杨长老 刑侦高考:如何用SQL解决环环相扣的刑侦推理问题 之后,苏旭辉的一个版本,希望大家能够在高手的过招中,看到喜爱、坚持、执着与技艺。

932

扫码关注云+社区