add a solution for 735

fishercoder1534 · fishercoder1534 · commit e338d1d16731 · 2021-11-04T16:57:47.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_735.java b/src/main/java/com/fishercoder/solutions/_735.java
@@ -1,11 +1,12 @@
 package com.fishercoder.solutions;
 
-import java.util.Stack;
+import java.util.Deque;
+import java.util.LinkedList;
 
 public class _735 {
     public static class Solution1 {
         public int[] asteroidCollision(int[] asteroids) {
-            Stack<Integer> stack = new Stack();
+            Deque<Integer> stack = new LinkedList<>();
             for (int i = 0; i < asteroids.length; i++) {
                 if (!stack.isEmpty() && stack.peek() > 0 && asteroids[i] < 0) {
                     if (Math.abs(stack.peek()) < Math.abs(asteroids[i])) {
@@ -27,7 +28,7 @@ public int[] asteroidCollision(int[] asteroids) {
             return result;
         }
 
-        private void collide(Stack<Integer> stack) {
+        private void collide(Deque<Integer> stack) {
             do {
                 Integer top = stack.pop();
                 if (!stack.isEmpty() && stack.peek() * top < 0) {
@@ -47,4 +48,43 @@ private void collide(Stack<Integer> stack) {
             } while (!stack.isEmpty());
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely original solution on 11/5/2021.
+         */
+        public int[] asteroidCollision(int[] asteroids) {
+            Deque<Integer> stack = new LinkedList<>();
+            for (int a : asteroids) {
+                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 {
+                            while (!stack.isEmpty() && stack.peekLast() > 0 && stack.peekLast() < Math.abs(a)) {
+                                stack.pollLast();
+                            }
+                            if (!stack.isEmpty() && stack.peekLast() > 0 && stack.peekLast() == Math.abs(a)) {
+                                stack.pollLast();
+                                continue;
+                            } else if (stack.isEmpty() || stack.peekLast() < 0) {
+                                stack.addLast(a);
+                            }
+                        }
+                    } else {
+                        stack.addLast(a);
+                    }
+                }
+            }
+            int[] ans = new int[stack.size()];
+            for (int i = stack.size() - 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
@@ -8,18 +8,22 @@
 
 public class _735Test {
     private static _735.Solution1 solution1;
+    private static _735.Solution2 solution2;
     private static int[] asteroids;
+    private static int[] expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _735.Solution1();
+        solution2 = new _735.Solution2();
     }
 
     @Test
     public void test1() {
         asteroids = new int[]{5, 10, -5};
-        asteroids = solution1.asteroidCollision(asteroids);
-        assertArrayEquals(new int[]{5, 10}, asteroids);
+        expected = new int[]{5, 10};
+        assertArrayEquals(expected, solution1.asteroidCollision(asteroids));
+        assertArrayEquals(expected, solution2.asteroidCollision(asteroids));
     }
 
     @Test
