题目
给定一个整数数组 asteroids,表示在同一行的行星。
对于数组中的每一个元素,其绝对值表示行星的大小,正负表示行星的移动方向(正表示向右移动,负表示向左移动)。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则:两个行星相互碰撞,较小的行星会爆炸。如果两颗行星大小相同,则两颗行星都会爆炸。两颗移动方向相同的行星,永远不会发生碰撞。
示例
示例 1:
输入:asteroids = [5,10,-5]
输出:[5,10]
解释:10 和 -5 碰撞后只剩下 10 。 5 和 10永远不会发生碰撞。
示例 2:
输入:asteroids = [8,-8]
输出:[]
解释:8 和 -8 碰撞后,两者都发生爆炸。
示例 3:
输入:asteroids = [10,2,-5]
输出:[10]
解释:2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下10 。
提示:
2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
思路
1.扫描一遍给定数组,记录数值为负的值的下标
2.使用队列,按顺序从小到大弹出值为负的下标
3.依次从该下标和前方所有元素相比较
4.若前方元素为负,永远不会相撞,直接跳过该下标
5.若前方元素为正,比较两元素绝对值,若负数绝对值较大,删除前方元素,继续往前比较。若正数绝对值大,删除负数元素,跳到下一个负数开始比较。若两数绝对值相等,删除两元素,跳到下一个负数比较
6.由于边比较边删除比较复杂,这里使用了几个小技巧,下标需要使用相对下标,详细见代码。
题解
class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: # 负数元素队列 temp = deque() for i in range(len(asteroids)): if asteroids[i] < 0: temp.append(i) # 负数下标需要减去的相对值 ans = 0 # 弹出负数下标比较 while temp: # 变为相对负数下标 index = temp.popleft() - ans # 记录需要删除的下标 res = [] for i in range(index - 1, -1, -1): if asteroids[i] < 0: break else: if abs(asteroids[index]) > abs(asteroids[i]): res.append(i) elif abs(asteroids[index]) < abs(asteroids[i]): res.append(index) break else: res.append(i) res.append(index) break # 按下标由小到大的顺序删除 res = sorted(res) for i in range(len(res)): # 每删除一个元素,负数下标需要剪的相对值也要加1 # 第一个元素直接删除 if i == 0: asteroids.pop(res[i]) ans +=1 # 其他元素减去相对值i else: asteroids.pop(res[i] - i) ans += 1 return asteroids