杭州网站优化培训,网站推广排名收费,企业管理软件开发工具,成品软件网站大全推荐1.题目描述
735. 行星碰撞
给定一个整数数组 asteroids#xff0c;表示在同一行的行星。
对于数组中的每一个元素#xff0c;其绝对值表示行星的大小#xff0c;正负表示行星的移动方向#xff08;正表示向右移动#xff0c;负表示向左移动#xff09;。每一颗行星以相…1.题目描述
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 。2.解题思路与代码
2.1 解题思路
题目说正数行星向右运动负数行星向左运动那么当数组中遇到负数时就需要与该数前面的正数进行比较如果前面是正数那么发生碰撞留下绝对值较大的绝对值相等则抵消两数消失。根据这一思路使用栈进行解答。遍历数组如果当前数大于 0 并且栈顶元素小于 0那么就需要弹出栈顶元素与当前数进行比较就会有以下三种情况
如果当前元素绝对值大于弹出元素绝对值选择当前元素继续弹出栈顶元素进行比较如果当前元素绝对值小于弹出元素绝对值选择弹出元素并退出循环弹出元素重新入栈如果当前元素绝对值等于弹出元素绝对值两数同时消失
下面用题目示例 [5, 10, -5] 进行图解 首先 index0 指向 5此时栈为空直接入栈 index 右移此时 index 指向元素和栈顶元素都大于 0方向相同不会碰撞直接入栈 index 右移此时 index 指向 -5栈顶元素为 10会发生碰撞因此弹出栈顶 10 与 -5 进行比较10 的绝对值大于 -5 的绝对值因此 -5 消失留下 10。循环这一步当前元素为 10 栈顶为 5 不会发生碰撞10 重新入栈 数组遍历完成最后栈中留下 5 和 10 位最终答案
由于答案需要返回一个数组为了便于最终将结果转数组因此代码中使用数组模拟栈同样也可以使用双端队列来做。
2.2 代码
class Solution {public int[] asteroidCollision(int[] asteroids) {// 为便于返回结果数组使用数组模拟栈int[] stack new int[asteroids.length];int idx -1;// 开始时将数组第一个元素入栈stack[idx] asteroids[0];int index 1;while (index asteroids.length) {Integer chooseNum asteroids[index];// 当选择数字小于 0栈顶数字大于 0 时会发生碰撞需要进行处理while (idx -1 chooseNum 0 stack[idx] 0) {// 弹出栈顶数字Integer pop stack[idx--];if (Math.abs(chooseNum) pop) {// 如果选择的数绝对值大于弹出栈的数绝对值则保留选择的数继续循环continue;} else if (Math.abs(chooseNum) pop) {// 如果选择的数绝对值小于弹出栈的数绝对值选择数字改为弹出的数字// 下次循环条件判断不通过退出循环后直接重新入栈chooseNum pop;} else {// 如果选择的数绝对值等于弹出栈的数绝对值两数同时消失chooseNum 置 nullchooseNum null;break;}}if (chooseNum ! null) {stack[idx] chooseNum;}index;}int[] ans new int[idx 1];System.arraycopy(stack, 0, ans, 0, idx 1);return ans;}
}2.3 测试结果
通过测试 3.总结
使用栈进行解答当元素大于 0栈顶元素小于 0 时会发生碰撞此时需要处理处理时比较当前元素和弹出栈元素的绝对值大小绝对值大的保留并循环比较保留数和栈顶元素的情况
