Skip to content

Commit e30cbb2

Browse files
add 54
1 parent ba6a191 commit e30cbb2

File tree

4 files changed

+104
-70
lines changed

4 files changed

+104
-70
lines changed

README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -377,7 +377,7 @@ Your ideas/fixes/algorithms are more than welcome!
377377
|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|
378378
|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|
379379
|55|[Jump Game](https://leetcode.com/problems/jump-game/)|[Solution](../master/src/main/java/com/stevesun/solutions/JumpGame.java)|O(n)|O(1)|Medium|
380-
|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|
380+
|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
381381
|53|[Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)|[Solution](../master/src/main/java/com/stevesun/solutions/MaximumSubarray.java)|O(n)|O(1)|Medium|
382382
|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|
383383
|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

src/main/java/com/stevesun/solutions/SpiralMatrix.java

Lines changed: 0 additions & 69 deletions
This file was deleted.
Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package com.stevesun.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
8+
9+
For example,
10+
Given the following matrix:
11+
12+
[
13+
[ 1, 2, 3 ],
14+
[ 4, 5, 6 ],
15+
[ 7, 8, 9 ]
16+
]
17+
You should return [1,2,3,6,9,8,7,4,5].
18+
*/
19+
public class _54 {
20+
21+
//credit: https://discuss.leetcode.com/topic/3713/super-simple-and-easy-to-understand-solution
22+
public List<Integer> spiralOrder(int[][] matrix) {
23+
List<Integer> result = new ArrayList();
24+
int row = matrix.length;
25+
26+
if (row == 0) {
27+
return result;
28+
}
29+
int rowStart = 0;
30+
int rowEnd = matrix.length-1;
31+
int colStart = 0;
32+
int colEnd = matrix[0].length-1;
33+
while (rowStart <= rowEnd && colStart <= colEnd) {
34+
//traverse to the right
35+
for (int j = colStart; j <= colEnd; j++) {
36+
result.add(matrix[rowStart][j]);
37+
}
38+
rowStart++;
39+
40+
//traverse to the bottom
41+
for (int i = rowStart; i <= rowEnd; i++) {
42+
result.add(matrix[i][colEnd]);
43+
}
44+
colEnd--;
45+
46+
//only when rowStart <= rowEnd
47+
//we'll traverse to the left
48+
if (rowStart <= rowEnd) {
49+
for (int j = colEnd; j >= colStart; j--) {
50+
result.add(matrix[rowEnd][j]);
51+
}
52+
}
53+
rowEnd--;
54+
55+
//only when colStart <= colEnd
56+
//we'll traverse to the top
57+
if (colStart <= colEnd) {
58+
for (int i = rowEnd; i >= rowStart; i--) {
59+
result.add(matrix[i][colStart]);
60+
}
61+
}
62+
colStart++;
63+
}
64+
return result;
65+
}
66+
67+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.solutions._54;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import java.util.ArrayList;
8+
import java.util.Arrays;
9+
import java.util.List;
10+
11+
import static org.junit.Assert.assertEquals;
12+
13+
/**
14+
* Created by stevesun on 5/13/17.
15+
*/
16+
public class _54Test {
17+
private static _54 test;
18+
private static int[][] matrix;
19+
private static List<Integer> expected;
20+
21+
@BeforeClass
22+
public static void setup(){
23+
test = new _54();
24+
}
25+
26+
@Test
27+
public void test1(){
28+
matrix = new int[][]{
29+
{1,2,3},
30+
{4,5,6},
31+
{7,8,9},
32+
};
33+
expected = new ArrayList(Arrays.asList(1,2,3,6,9,8,7,4,5));
34+
assertEquals(expected, test.spiralOrder(matrix));
35+
}
36+
}

0 commit comments

Comments
 (0)