題目描述
給定一個整數陣列 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499065.html
標籤：其他
上一篇：開源原始碼商城系統盤點
下一篇：無線通信中LoRa技術特點