小行星的碰撞 |
您所在的位置:网站首页 › 小行星的意义 › 小行星的碰撞 |
给定一个整数数组,代表一行小行星。对于每个小行星,绝对值表示其大小,符号表示其方向(正意义右,负意义左)。 每个小行星以相同的速度移动。返回所有碰撞发生后小行星的状态。 如果两颗小行星相遇,则较小的小行星会爆炸。 如果两者的大小相同,则两者都会爆炸。 沿同一方向移动的两颗小行星永远不会相遇。
asteroid-collision 样例 样例 1: 输入: [5, 10, -5] 输出: [5, 10] 解释: 10 和 -5 碰撞得 10. 而 5 和 10 永远不会碰撞.样例 2: 输入: [10, 2, -5] 输出: [10] 解释: 2 和 -5 碰撞后得到 -5. 然后 10 和 -5 碰撞剩下10.思路 1、使用 stack 来解题 2、循环数组 item 1、如果大于 0 直接入栈 2、如果小于 0 遍历非空 stach 如果 栈顶大于 0 并且栈顶小于item 的绝对值,则出栈 3、如果栈为空 或者 栈顶小于 0 入栈 4、如果 item 跟栈顶相加为 0 则出栈
public class Solution { /** * @param asteroids: a list of integers * @return: return a list of integers */ public int[] asteroidCollision(int[] asteroids) { // write your code here Stack stack = new Stack(); for (int item : asteroids) { if (item > 0) { stack.push(item); } else { while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < Math.abs(item)) { stack.pop(); } if (stack.isEmpty() || stack.peek() < 0) { stack.push(item); } else if (item + stack.peek() == 0) { stack.pop(); } } } int[] result = new int[stack.size()]; for (int i = stack.size() - 1; i >= 0; i--) { result[i] = stack.pop(); } return result; } } 源码地址: https://github.com/xingfu0809/Java-LintCode |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |