[LC735]行星碰撞
2022/7/14 6:20:17
本文主要是介绍[LC735]行星碰撞,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给定一个整数数组 asteroids,表示在同一行的行星。对于数组中的每一个元素,其绝对值表示行星的大小,正负表示行星的移动方向(正表示向右移动,负表示向左移动)。每一颗行星以相同的速度移动。找出碰撞后剩下的所有行星。碰撞规则:两个行星相互碰撞,较小的行星会爆炸。如果两颗行星大小相同,则两颗行星都会爆炸。两颗移动方向相同的行星,永远不会发生碰撞。[题目地址]
思路与代码
对题目进行简单分析后发现,行星碰撞是具有延续性质的,换句话说,当相邻的两个行星发生碰撞后,其中的一个行星会消失,继续存在的行星若和新的相邻行星也符合碰撞条件,则能继续地进行碰撞。另外,还可以发现,不论以从左到右或是从右到左,或是其他顺序。只要星星之间的相对位置不变,其最终结果不变。这样两个特点,很自然想到用使用栈作为基本的数据结构,并模拟其碰撞的规则。
点击查看代码
public int[] asteroidCollision(int[] asteroids) { Deque<Integer> stack = new ArrayDeque(); //check every aster from left to right for(int aster : asteroids){ boolean addNewAster = true; //keep check until this aster is dead or there is no collision to happen while(addNewAster && !stack.isEmpty() && stack.peekLast() > 0 && aster < 0){ int lastAster = stack.peekLast(), copyAster = -aster; if(lastAster <= copyAster) stack.pollLast(); if(lastAster >= copyAster) addNewAster = false; } if(addNewAster) stack.addLast(aster); } int[] rtn = new int[stack.size()]; for(int i = 0; i < rtn.length ; i++){ rtn[i] = stack.pollFirst(); } return rtn; }
这篇关于[LC735]行星碰撞的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享