Java实现 LeetCode 735 行星碰撞（栈）
2024-09-03 23:59:32
735. 行星碰撞
给定一个整数数组 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 向右移动。
由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
说明:
数组 asteroids 的长度不超过 10000。
每一颗行星的大小都是非零整数，范围是 [-1000, 1000] 。
PS：
用栈会慢一点，还是数组快一些，栈运行的是6ms，数组是1ms，既然动动手能提高效率，肯定要提高一下了，
(●ˇ∀ˇ●)
class Solution {
public int[] asteroidCollision(int[] arr) {
// stack
int n = arr.length;
int[] stack = new int[n];
int stackSize = 0;
for (int num : arr) {
if (num > 0) {
stack[stackSize++] = num;
} else {
while (stackSize > 0 && stack[stackSize - 1] > 0 && stack[stackSize - 1] < -num) {
stackSize--;
}
if (stackSize == 0) {
stack[stackSize++] = num;
} else {
int top = stack[stackSize - 1];
if (top < 0) {
stack[stackSize++] = num;
} else if (top == -num) {
stackSize--;
}
}
}
}
return Arrays.copyOf(stack, stackSize);
}
}
最新文章
- selenium问题记录
- 利用JDK（1.6及以上版本）创建WebService
- TabHost Tab的添加和删除
- -AC自动机-题表
- htm跨域锚点定位
- JS表格排序
- 使用Docker容器来源码编译etcd
- windows安装nvm管理node版本
- 使用abcpdf分页设置的问题
- 6.JAVA基础复习——JAVA中文档注释与帮助文档的生成
- Luogu P4248 [AHOI2013]差异
- 什么是webservice？
- 躲不掉的 lambda 表达式
- C# 读取Excel和DBF文件
- textarea 标签换行及靠左
- jenkins 的一个BUG
- InvocationHandler中invoke方法中的第一个参数proxy的用途
- DATAGUARD的搭建
- Andorid之使用GMail后台偷偷发送邮件(不要干坏事噢=。 =)
- 【算法笔记】B1025 反转链表