聊城網(wǎng)站優(yōu)化信息網(wǎng)頁廣告
1.題目描述
735. 行星碰撞
給定一個整數(shù)數(shù)組 asteroids,表示在同一行的行星。
對于數(shù)組中的每一個元素,其絕對值表示行星的大小,正負(fù)表示行星的移動方向(正表示向右移動,負(fù)表示向左移動)。每一顆行星以相同的速度移動。
找出碰撞后剩下的所有行星。碰撞規(guī)則:兩個行星相互碰撞,較小的行星會爆炸。如果兩顆行星大小相同,則兩顆行星都會爆炸。兩顆移動方向相同的行星,永遠(yuǎn)不會發(fā)生碰撞。
示例 1:
輸入:asteroids = [5,10,-5]
輸出:[5,10]
解釋:10 和 -5 碰撞后只剩下 10 。 5 和 10 永遠(yuǎn)不會發(fā)生碰撞。
示例 2:
輸入:asteroids = [8,-8]
輸出:[]
解釋:8 和 -8 碰撞后,兩者都發(fā)生爆炸。
示例 3:
輸入:asteroids = [10,2,-5]
輸出:[10]
解釋:2 和 -5 發(fā)生碰撞后剩下 -5 。10 和 -5 發(fā)生碰撞后剩下 10 。
2.解題思路與代碼
2.1 解題思路
題目說正數(shù)行星向右運(yùn)動,負(fù)數(shù)行星向左運(yùn)動,那么當(dāng)數(shù)組中遇到負(fù)數(shù)時,就需要與該數(shù)前面的正數(shù)進(jìn)行比較,如果前面是正數(shù),那么發(fā)生碰撞留下絕對值較大的;絕對值相等則抵消,兩數(shù)消失。根據(jù)這一思路,使用棧進(jìn)行解答。遍歷數(shù)組如果當(dāng)前數(shù)大于 0 ,并且棧頂元素小于 0,那么就需要彈出棧頂元素與當(dāng)前數(shù)進(jìn)行比較,就會有以下三種情況:
- 如果當(dāng)前元素絕對值大于彈出元素絕對值,選擇當(dāng)前元素,繼續(xù)彈出棧頂元素進(jìn)行比較;
- 如果當(dāng)前元素絕對值小于彈出元素絕對值,選擇彈出元素并退出循環(huán),彈出元素重新入棧
- 如果當(dāng)前元素絕對值等于彈出元素絕對值,兩數(shù)同時消失
下面用題目示例 [5, 10, -5] 進(jìn)行圖解:
-
首先 index=0 指向 5,此時棧為空直接入棧
-
index 右移,此時 index 指向元素和棧頂元素都大于 0,方向相同不會碰撞直接入棧
-
index 右移,此時 index 指向 -5,棧頂元素為 10,會發(fā)生碰撞因此彈出棧頂 10 與 -5 進(jìn)行比較,10 的絕對值大于 -5 的絕對值,因此 -5 消失留下 10。循環(huán)這一步,當(dāng)前元素為 10 棧頂為 5 不會發(fā)生碰撞,10 重新入棧
-
數(shù)組遍歷完成,最后棧中留下 5 和 10 位最終答案
由于答案需要返回一個數(shù)組,為了便于最終將結(jié)果轉(zhuǎn)數(shù)組因此代碼中使用數(shù)組模擬棧,同樣也可以使用雙端隊列來做。
2.2 代碼
class Solution {public int[] asteroidCollision(int[] asteroids) {// 為便于返回結(jié)果數(shù)組,使用數(shù)組模擬棧int[] stack = new int[asteroids.length];int idx = -1;// 開始時將數(shù)組第一個元素入棧stack[++idx] = asteroids[0];int index = 1;while (index < asteroids.length) {Integer chooseNum = asteroids[index];// 當(dāng)選擇數(shù)字小于 0,棧頂數(shù)字大于 0 時會發(fā)生碰撞,需要進(jìn)行處理while (idx > -1 && chooseNum < 0 && stack[idx] > 0) {// 彈出棧頂數(shù)字Integer pop = stack[idx--];if (Math.abs(chooseNum) > pop) {// 如果選擇的數(shù)絕對值大于彈出棧的數(shù)絕對值,則保留選擇的數(shù),繼續(xù)循環(huán)continue;} else if (Math.abs(chooseNum) < pop) {// 如果選擇的數(shù)絕對值小于彈出棧的數(shù)絕對值,選擇數(shù)字改為彈出的數(shù)字// 下次循環(huán)條件判斷不通過,退出循環(huán)后直接重新入棧chooseNum = pop;} else {// 如果選擇的數(shù)絕對值等于彈出棧的數(shù)絕對值,兩數(shù)同時消失,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 測試結(jié)果
通過測試
3.總結(jié)
- 使用棧進(jìn)行解答
- 當(dāng)元素大于 0,棧頂元素小于 0 時會發(fā)生碰撞,此時需要處理
- 處理時比較當(dāng)前元素和彈出棧元素的絕對值大小,絕對值大的保留,并循環(huán)比較保留數(shù)和棧頂元素的情況