Leetcode 735 ：行星碰撞——详细分析及python实现

问题描述：

给定一个整数数组 asteroids，表示在同一行的行星。

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

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

来源：力扣（LeetCode）

 分析：

1、只有行星相向才可能发生碰撞，即[5, -5]发生碰撞，[-5, 5]不发生碰撞

2、由第3个例子获得思路每次仅发生一次碰撞，定义函数check_neighbor()查找每次发生碰撞的第一个行星位置，若找不到则返回当前list

3、对于每次发生碰撞的两个行星，可以确定第一个行星(index)为正，第二个(index+1)为负，故比较其绝对值即可确定淘汰下来哪个行星

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        def check_neighbor(asteroids):                                      # 内部函数
            for index in range(len(asteroids) - 1):
                if asteroids[index] > 0 and asteroids[index + 1] < 0:       # 只有相向而行的时候才发生碰撞
                    return index                                            # 发生碰撞的第一个行星位置
            return -1                                                       # 当前数组已不能发生碰撞
        while(check_neighbor(asteroids) != -1):                             # 不能在发生碰撞时退出
            index = check_neighbor(asteroids)                               # 获取发生碰撞的位置
            if asteroids[index] > -asteroids[index + 1]:                    # 删除碰撞处绝对值小的行星
                asteroids.pop(index + 1)
            elif asteroids[index] < -asteroids[index + 1]:
                asteroids.pop(index)
            else:
                asteroids.pop(index + 1)                                    # 两个行星值相等时，都删除，顺序不能调换
                asteroids.pop(index)
        return asteroids                                                    # 不再能发生碰撞