→ ILoveErr: 大師 07/21 01:29
→ Rushia: 大師 07/21 02:02
※ 編輯: yam276 (60.248.143.172 臺灣), 07/21/2023 10:32:50
735. Asteroid Collision
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign
represents its direction (positive meaning right, negative meaning left). Each
asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids
meet, the smaller one will explode. If both are the same size, both will
explode. Two asteroids moving in the same direction will never meet.
小行星有體積(數字大小)跟飛行方向(正負號)，飛行方向相撞會比大小決定誰留著。
Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Example 2:
Input: asteroids = [8,-8]
Output: []
Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Step:
用Stack解比較方便
題目說明可以看這個：https://www.youtube.com/watch?v=LN7KjRszjk4
建立Stack
│
for遍歷小行星陣列
│
└── while判斷是否碰撞
│ ├─ 條件1: Stack不為空
│ ├─ 條件2: 左小行星向右移動
│ ├─ 條件3: 右小行星向左移動
│ │
│ if發生碰撞的處理
│ ├─ 右邊小行星較大
│ │ └─ 左小行星毀損，從Stack把左小行星移除
│ ├─ 左邊小行星較大
│ │ └─ 右小行星損毀，大小設為0
│ ├─ 一樣大
│ │ └─ 兩顆都毀損，從Stack移除左，右大小設為0
│ │
│ if如果判斷結束右小行星還在
│ └─ 加入Stack，跑下一輪while
│
└─ for最後記得把Stack轉回Vector以return
Code:
沒Rust 明天再寫
class Solution
{
public:
vector<int> asteroidCollision(vector<int>& asteroids)
{
stack<int> result;
for (int i = 0; i < asteroids.size(); i++)
{
int right_asteroid = asteroids[i];
while (!result.empty() &&
result.top() > 0 &&
right_asteroid < 0)
{
int left_asteroid = result.top();
if (left_asteroid < -right_asteroid)
{
result.pop();
}
else if (left_asteroid == -right_asteroid)
{
result.pop();
right_asteroid = 0;
}
else
{
right_asteroid = 0;
break;
}
}
if (right_asteroid)
result.push(right_asteroid);
}
vector<int> output(result.size());
for(int i = result.size() - 1; i >= 0; i--)
{
output[i] = result.top();
result.pop();
}
return output;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689872841.A.3B6.html