小白刷不停 735 ~ 行星相撞
基本信息
- 题号:735
- 题厂:lya
- 难度系数:中
数组 asteroid 代表一些行星,正数代表星星右行,负数代表星星左行……星星不能为 0。
如果两行星发生撞击,绝对值较小的撞没;如果绝对值相等,则 2 个一起被撞没……
例如:asteroids = [10,2,-5],返回 [10] 2 ~ -5 发生相撞,-5 绝对值较大,2 被撞没;-5 继续前行和 10 发生相撞,10 绝对值较大,这次 -5 被撞没
解题思路
- 撞击 ~ 即在数组内部发生配对问题——此类问题一般采用 stack 先进后出原理解决。例如脸书著名 #20 括号判断问题,都是异曲同工的思路模型
- 分析相撞条件:只有前右行(正数)后左行(负数)的条件下才可能发生撞击
- 当 stack 为空时,无论正数负数,都不会发生撞击
- 当遇上正数时,是不会发生撞击的
- 只有遇上负数,且 stack 最后一个元素为正时,撞击才会发生
- 检测撞击后,还需要进一步分析:
- 相撞 2 星绝对值相等还是不相等;
- 以及循环撞击问题。即 stack 被 pop 后下一个元素还为正时
class Solution: def asteroidCollision(self, asteroids: List[int]) -> List[int]: stack = [] for a in asteroids: while stack and a < 0 and stack[-1] > 0: diff = a + stack[-1] # 撞击发生后,我们通过重置 a = 0 解决达到当前行星绝对值较小或者相等的问题 # 剩下的绝对值比较问题,则 stack 不断 pop 就好…… if diff < 0: stack.pop() elif diff > 0: a = 0 else: a = 0 stack.pop() # 如果没有发生撞击,或者当前行星没有因为绝对值较小已经被撞没(重设 a = 0 了),还需要把 a 添加进 stack…… if a != 0: stack.append(a) return stack
Constraints
2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
本题告知 「行星」不为 0;考试时可就此取值问题与考官讨论确认。
Big O
- Time:O(n)
- Space:O(n), stack 引入
测试
- 相等行星相撞时
- 不等相撞时,发生循环相撞
- 不发生相撞时
- 因为不断相撞导致 stack 为空的情况
- ……
总结
- 如果熟悉 stack 原理及 stack 适合解决的套路问题,还是会比较容易想出解法
- 一旦想到需要引用 stack 解题,剩下的逻辑判断相对容易
- 但就各种撞击情况的判断问题,考察仔细思维严密性,以及解题后的各种测试分析