add a solution for 735

fishercoder1534 · fishercoder1534 · commit 9dc51ae3f3a6 · 2022-01-14T10:31:01.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_735.java b/src/main/java/com/fishercoder/solutions/_735.java
@@ -87,4 +87,37 @@ public int[] asteroidCollision(int[] asteroids) {
             return ans;
         }
     }
+
+    public static class Solution3 {
+        /**
+         * My completely original solution on 1/14/2022.
+         */
+        public int[] asteroidCollision(int[] asteroids) {
+            Deque<Integer> stack = new LinkedList<>();
+            for (int i = 0; i < asteroids.length; i++) {
+                int a = asteroids[i];
+                if (a > 0) {
+                    stack.addLast(a);
+                } else {
+                    if (!stack.isEmpty() && stack.peekLast() > 0) {
+                        if (stack.peekLast() > Math.abs(a)) {
+                            continue;
+                        } else if (stack.peekLast() == Math.abs(a)) {
+                            stack.pollLast();
+                        } else {
+                            stack.pollLast();
+                            i--;
+                        }
+                    } else {
+                        stack.addLast(a);
+                    }
+                }
+            }
+            int[] ans = new int[stack.size()];
+            for (int i = ans.length - 1; i >= 0; i--) {
+                ans[i] = stack.pollLast();
+            }
+            return ans;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_735Test.java b/src/test/java/com/fishercoder/_735Test.java
@@ -9,13 +9,15 @@
 public class _735Test {
     private static _735.Solution1 solution1;
     private static _735.Solution2 solution2;
+    private static _735.Solution3 solution3;
     private static int[] asteroids;
     private static int[] expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _735.Solution1();
         solution2 = new _735.Solution2();
+        solution3 = new _735.Solution3();
     }
 
     @Test
@@ -24,6 +26,7 @@ public void test1() {
         expected = new int[]{5, 10};
         assertArrayEquals(expected, solution1.asteroidCollision(asteroids));
         assertArrayEquals(expected, solution2.asteroidCollision(asteroids));
+        assertArrayEquals(expected, solution3.asteroidCollision(asteroids));
     }
 
     @Test
