add 946

fishercoder1534 · fishercoder1534 · commit da2e739320e3 · 2020-02-12T20:49:24.000-08:00
diff --git a/README.md b/README.md
@@ -143,6 +143,7 @@ _If you like this project, please leave me a star._ &#9733;
 |953|[Verifying an Alien Dictionary](https://leetcode.com/problems/verifying-an-alien-dictionary/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_953.java)| |Easy|
 |951|[Flip Equivalent Binary Trees](https://leetcode.com/problems/flip-equivalent-binary-trees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_951.java) | |Medium| Tree, DFS, recursion|
 |950|[Reveal Cards In Increasing Order](https://leetcode.com/problems/reveal-cards-in-increasing-order/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_950.java) | |Medium|
+|946|[Validate Stack Sequences](https://leetcode.com/problems/validate-stack-sequences/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_946.java) | |Medium|Stack
 |944|[Delete Columns to Make Sorted](https://leetcode.com/problems/delete-columns-to-make-sorted/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_944.java) | |Easy|
 |942|[DI String Match](https://leetcode.com/problems/di-string-match/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_942.java) | |Easy|
 |941|[Valid Mountain Array](https://leetcode.com/problems/valid-mountain-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_941.java) | |Easy|
@@ -165,6 +166,7 @@ _If you like this project, please leave me a star._ &#9733;
 |888|[Fair Candy Swap](https://leetcode.com/problems/fair-candy-swap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_888.java) |  |Easy|
 |885|[Spiral Matrix III](https://leetcode.com/problems/spiral-matrix-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_885.java)  |[:tv:](https://www.youtube.com/watch?v=0qep3f9cqVs) |Medium|
 |884|[Uncommon Words from Two Sentences](https://leetcode.com/problems/uncommon-words-from-two-sentences/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_884.java) | |Easy|
+|883|[Projection Area of 3D Shapes](https://leetcode.com/problems/projection-area-of-3d-shapes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_883.java) | |Easy|Math
 |876|[Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_876.java) | |Easy|
 |872|[Leaf-Similar Trees](https://leetcode.com/problems/leaf-similar-trees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_872.java) |  |Easy| DFS, recursion
 |868|[Binary Gap](https://leetcode.com/problems/binary-gap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_868.java) |  |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_946.java b/src/main/java/com/fishercoder/solutions/_946.java
@@ -0,0 +1,54 @@
+package com.fishercoder.solutions;
+
+import java.util.Stack;
+
+/**
+ * 946. Validate Stack Sequences
+ *
+ * Given two sequences pushed and popped with distinct values,
+ * return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.
+ *
+ * Example 1:
+ * Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
+ * Output: true
+ * Explanation: We might do the following sequence:
+ * push(1), push(2), push(3), push(4), pop() -> 4,
+ * push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
+ *
+ * Example 2:
+ * Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
+ * Output: false
+ * Explanation: 1 cannot be popped before 2.
+ *
+ * Note:
+ * 0 <= pushed.length == popped.length <= 1000
+ * 0 <= pushed[i], popped[i] < 1000
+ * pushed is a permutation of popped.
+ * pushed and popped have distinct values.
+ * */
+public class _946 {
+    public static class Solution1 {
+        public boolean validateStackSequences(int[] pushed, int[] popped) {
+            if (pushed == null || popped == null || pushed.length == 0 || popped.length == 0) {
+                return true;
+            }
+            Stack<Integer> stack = new Stack<>();
+            stack.push(pushed[0]);
+            int i = 1;
+            int j = 0;
+            while (!stack.isEmpty() || j < popped.length) {
+                if (j < popped.length && !stack.isEmpty() && stack.peek() == popped[j]) {
+                    stack.pop();
+                    j++;
+                } else {
+                    if (i < pushed.length) {
+                        stack.push(pushed[i++]);
+                    } else {
+                        return stack.isEmpty();
+                    }
+                }
+            }
+            return stack.isEmpty();
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_946Test.java b/src/test/java/com/fishercoder/_946Test.java
@@ -0,0 +1,37 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._946;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _946Test {
+
+    private static _946.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _946.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(true, solution1.validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 5, 3, 2, 1}));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(false, solution1.validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 3, 5, 1, 2}));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(true, solution1.validateStackSequences(new int[]{}, new int[]{}));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals(false, solution1.validateStackSequences(new int[]{4, 0, 1, 2, 3}, new int[]{4, 2, 3, 0, 1}));
+    }
+}
