add 54

fishercoder1534 · fishercoder1534 · commit e30cbb22d4ad · 2017-05-13T10:06:30.000-07:00
diff --git a/README.md b/README.md
@@ -377,7 +377,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |58|[Length of Last Word](https://leetcode.com/problems/length-of-last-word/)|[Solution](../master/src/main/java/com/stevesun/solutions/LengthofLastWord.java)|O(n)|O(1)|Easy|
 |56|[Merge Intervals](https://leetcode.com/problems/merge-intervals/)|[Solution](../master/src/main/java/com/stevesun/solutions/MergeIntervals.java)|O(n*logn)|O(1)|Hard|
 |55|[Jump Game](https://leetcode.com/problems/jump-game/)|[Solution](../master/src/main/java/com/stevesun/solutions/JumpGame.java)|O(n)|O(1)|Medium|
-|54|[Spiral Matrix](https://leetcode.com/problems/spiral-matrix/)|[Solution](../master/src/main/java/com/stevesun/solutions/SpiralMatrix.java)|O(m*n)|O(m*n)|Medium|
+|54|[Spiral Matrix](https://leetcode.com/problems/spiral-matrix/)|[Solution](../master/src/main/java/com/stevesun/solutions/_54.java)|O(m*n)|O(m*n)|Medium| Array
 |53|[Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)|[Solution](../master/src/main/java/com/stevesun/solutions/MaximumSubarray.java)|O(n)|O(1)|Medium|
 |50|[Pow(x, n)](https://leetcode.com/problems/powx-n/)|[Solution](../master/src/main/java/com/stevesun/solutions/PowXN.java)|O(logn)|O(logn)|Medium|
 |48|[Rotate Image](https://leetcode.com/problems/rotate-image/)|[Solution](../master/src/main/java/com/stevesun/solutions/_48.java)|O(n^2)|O(1)|Medium|Array
diff --git a/src/main/java/com/stevesun/solutions/SpiralMatrix.java b/src/main/java/com/stevesun/solutions/SpiralMatrix.java
diff --git a/src/main/java/com/stevesun/solutions/_54.java b/src/main/java/com/stevesun/solutions/_54.java
@@ -0,0 +1,67 @@
+package com.stevesun.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
+
+ For example,
+ Given the following matrix:
+
+ [
+ [ 1, 2, 3 ],
+ [ 4, 5, 6 ],
+ [ 7, 8, 9 ]
+ ]
+ You should return [1,2,3,6,9,8,7,4,5].
+ */
+public class _54 {
+
+    //credit: https://discuss.leetcode.com/topic/3713/super-simple-and-easy-to-understand-solution
+    public List<Integer> spiralOrder(int[][] matrix) {
+        List<Integer> result = new ArrayList();
+        int row = matrix.length;
+
+        if (row == 0) {
+            return result;
+        }
+        int rowStart = 0;
+        int rowEnd = matrix.length-1;
+        int colStart = 0;
+        int colEnd = matrix[0].length-1;
+        while (rowStart <= rowEnd && colStart <= colEnd) {
+            //traverse to the right
+            for (int j = colStart; j <= colEnd; j++) {
+                result.add(matrix[rowStart][j]);
+            }
+            rowStart++;
+
+            //traverse to the bottom
+            for (int i = rowStart; i <= rowEnd; i++) {
+                result.add(matrix[i][colEnd]);
+            }
+            colEnd--;
+
+            //only when rowStart <= rowEnd
+            //we'll traverse to the left
+            if (rowStart <= rowEnd) {
+                for (int j = colEnd; j >= colStart; j--) {
+                    result.add(matrix[rowEnd][j]);
+                }
+            }
+            rowEnd--;
+
+            //only when colStart <= colEnd
+            //we'll traverse to the top
+            if (colStart <= colEnd) {
+                for (int i = rowEnd; i >= rowStart; i--) {
+                    result.add(matrix[i][colStart]);
+                }
+            }
+            colStart++;
+        }
+        return result;
+    }
+
+}
diff --git a/src/test/java/com/stevesun/_54Test.java b/src/test/java/com/stevesun/_54Test.java
@@ -0,0 +1,36 @@
+package com.stevesun;
+
+import com.stevesun.solutions._54;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Created by stevesun on 5/13/17.
+ */
+public class _54Test {
+    private static _54 test;
+    private static int[][] matrix;
+    private static List<Integer> expected;
+
+    @BeforeClass
+    public static void setup(){
+        test = new _54();
+    }
+
+    @Test
+    public void test1(){
+        matrix = new int[][]{
+                {1,2,3},
+                {4,5,6},
+                {7,8,9},
+        };
+        expected = new ArrayList(Arrays.asList(1,2,3,6,9,8,7,4,5));
+        assertEquals(expected, test.spiralOrder(matrix));
+    }
+}
