add 885

fishercoder1534 · fishercoder1534 · commit 8d7440243d07 · 2019-12-11T08:04:13.000-08:00
diff --git a/README.md b/README.md
@@ -106,6 +106,7 @@ _If you like this project, please leave me a star._ &#9733;
 |896|[Monotonic Array](https://leetcode.com/problems/monotonic-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_896.java) | O(n) | O(1) | |Easy|
 |890|[Find and Replace Pattern](https://leetcode.com/problems/find-and-replace-pattern/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_890.java) | O(n) | O(1) | |Medium|
 |888|[Fair Candy Swap](https://leetcode.com/problems/fair-candy-swap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_888.java) | O(n) | O(1) | |Easy|
+|885|[Spiral Matrix III](https://leetcode.com/problems/spiral-matrix-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_885.java) | |  | |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) | O(n) | O(k) | |Easy|
 |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) | O(n) | O(1) | |Easy|
 |872|[Leaf-Similar Trees](https://leetcode.com/problems/leaf-similar-trees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_872.java) | O(n) | O(h) | |Easy| DFS, recursion
diff --git a/src/main/java/com/fishercoder/solutions/_885.java b/src/main/java/com/fishercoder/solutions/_885.java
@@ -0,0 +1,59 @@
+package com.fishercoder.solutions;
+
+/**
+ * 885. Spiral Matrix III
+ *
+ * On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.
+ * Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.
+ * Now, we walk in a clockwise spiral shape to visit every position in this grid.
+ * Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)
+ * Eventually, we reach all R * C spaces of the grid.
+ * Return a list of coordinates representing the positions of the grid in the order they were visited.
+ *
+ * Example 1:
+ * Input: R = 1, C = 4, r0 = 0, c0 = 0
+ * Output: [[0,0],[0,1],[0,2],[0,3]]
+ *
+ * Example 2:
+ * Input: R = 5, C = 6, r0 = 1, c0 = 4
+ * Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
+ *
+ * Note:
+ * 1 <= R <= 100
+ * 1 <= C <= 100
+ * 0 <= r0 < R
+ * 0 <= c0 < C
+ * */
+public class _885 {
+    public static class Solution1 {
+        /**credit: https://leetcode.com/problems/spiral-matrix-iii/discuss/158977/Java-15-lines-concise-solution-with-comments*/
+        public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
+            int[][] directions = new int[][]{
+                    {0, 1},
+                    {1, 0},
+                    {0, -1},
+                    {-1, 0}
+            };
+            int[][] result = new int[R * C][2];
+            int j = 0;
+            result[j++] = new int[]{r0, c0};
+            int len = 0;
+            int d = 0;
+            while (j < R * C) {
+                if (d == 0 || d == 2) {
+                    //plus one when moving east or west
+                    len++;
+                }
+                for (int i = 0; i < len; i++) {
+                    r0 += directions[d][0];
+                    c0 += directions[d][1];
+                    if (r0 >= 0 && r0 < R && c0 >= 0 && c0 < C) {
+                        result[j++] = new int[]{r0, c0};
+                    }
+                }
+                d = (d + 1) % 4;
+            }
+            return result;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_885Test.java b/src/test/java/com/fishercoder/_885Test.java
@@ -0,0 +1,66 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._885;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class _885Test {
+    private static _885.Solution1 solution1;
+    private static int[][] expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _885.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        expected = new int[][]{
+                {0, 0},
+                {0, 1},
+                {0, 2},
+                {0, 3}
+        };
+        assertArrayEquals(expected, solution1.spiralMatrixIII(1, 4, 0, 0));
+    }
+
+    @Test
+    public void test2() {
+        expected = new int[][]{
+                {1, 4},
+                {1, 5},
+                {2, 5},
+                {2, 4},
+                {2, 3},
+                {1, 3},
+                {0, 3},
+                {0, 4},
+                {0, 5},
+                {3, 5},
+                {3, 4},
+                {3, 3},
+                {3, 2},
+                {2, 2},
+                {1, 2},
+                {0, 2},
+                {4, 5},
+                {4, 4},
+                {4, 3},
+                {4, 2},
+                {4, 1},
+                {3, 1},
+                {2, 1},
+                {1, 1},
+                {0, 1},
+                {4, 0},
+                {3, 0},
+                {2, 0},
+                {1, 0},
+                {0, 0}
+        };
+        assertArrayEquals(expected, solution1.spiralMatrixIII(5, 6, 1, 4));
+    }
+
+}
