aboutsummaryrefslogtreecommitdiff
path: root/asteroid_collision.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'asteroid_collision.cpp')
-rw-r--r--asteroid_collision.cpp52
1 files changed, 52 insertions, 0 deletions
diff --git a/asteroid_collision.cpp b/asteroid_collision.cpp
new file mode 100644
index 0000000..3597c8a
--- /dev/null
+++ b/asteroid_collision.cpp
@@ -0,0 +1,52 @@
+// 735. Asteroid Collision
+#include "leetcode.h"
+
+/*
+ * given an array 'asteroids' o intergers 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.
+ */
+
+class Solution {
+public:
+ vector<int> asteroidCollision(vector<int> &asteroids) {
+ int n = asteroids.size();
+ stack<int> s;
+ for (int i = 0; i < n; i++) {
+ if (asteroids[i] || s.empty())
+ s.push(asteroids[i]);
+ else {
+ while (!s.empty() && s.top() && s.top() < abs(asteroids[i]))
+ s.pop();
+ if (!s.empty() && s.top() == abs(asteroids[i]))
+ s.pop();
+ else if (s.empty() || s.top() < 0)
+ s.push(asteroids[i]);
+ }
+ }
+ vector<int> ans(s.size());
+ for (int i = (int)s.size() - 1; i >= 0; i--) {
+ ans[i] = s.top();
+ s.pop();
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<int> a1 = {5, 10, -5}, a2 = {8, -8}, a3 = {10, 2, -5};
+ for (auto i : obj.asteroidCollision(a1))
+ printf("%d ", i); // expect: 5 10
+ printf("\n");
+ for (auto i : obj.asteroidCollision(a2))
+ printf("%d ", i); // expect: nil
+ printf("\n");
+ for (auto i : obj.asteroidCollision(a3))
+ printf("%d ", i); // expect: 10
+ printf("\n");
+}