本文主要是介绍⭐北邮复试刷题LCR 037. 行星碰撞__栈 (力扣119经典题变种挑战),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
LCR 037. 行星碰撞
给定一个整数数组 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 。
示例 4:
输入:asteroids = [-2,-1,1,2]
输出:[-2,-1,1,2]
解释:-2 和 -1 向左移动,而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞,所以最终没有行星发生碰撞。
提示:
2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
题解:
本题借用栈来解决,只有±情况才会出现撞击,其余情况均会正常入栈,因此对±情况处理撞击,撞击可能会存在连环撞击,因此撞击完毕后需要回溯;
代码:
class Solution {public int[] asteroidCollision(int[] asteroids) {// 直到碰到第一个正数Stack<Integer> stack = new Stack<>();for(int i=0;i<asteroids.length;i++){if(stack.empty()){stack.push(asteroids[i]);continue;}int temp = stack.peek();if(temp < 0){stack.push(asteroids[i]);continue;}else if(temp > 0 && asteroids[i] > 0){stack.push(asteroids[i]);continue;}else{// 栈内有效可用数据绝对无负值if(Math.abs(asteroids[i]) > temp){stack.pop();// 回溯 因可能连环撞击i--;}else if(Math.abs(asteroids[i]) == temp){stack.pop();}else{continue;}}}// stack长度会随着pop动态改变 因此需要先拿到静态数据int len = stack.size();int res[] = new int[len];for(int i=0;i<len;i++){res[len-1-i] = stack.pop();}return res;}
}
结果:
这篇关于⭐北邮复试刷题LCR 037. 行星碰撞__栈 (力扣119经典题变种挑战)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!