My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return result;
int row = matrix.length;
int col = matrix[0].length;
for (int i = 0; i < Math.min(row, col); i++) {
int temp = spiralOrder(i, row - 2 * i, col - 2 * i, matrix, result);
if (temp == -1)
break;
}
return result;
}
private int spiralOrder(int begin, int rowCount, int colCount, int[][] matrix, ArrayList<Integer> result) {
if (rowCount <= 0 || colCount <= 0)
return -1;
else if (colCount == 1) {
for (int i = 0; i < rowCount; i++)
result.add(matrix[i + begin][begin]);
return -1;
}
else if (rowCount == 1) {
for (int i = 0; i < colCount; i++)
result.add(matrix[begin][i + begin]);
return -1;
}
int row = matrix.length - 1 - (matrix.length - rowCount) / 2;
int col = matrix[0].length - 1 - (matrix[0].length - colCount) / 2;
for (int i = begin; i <= col; i++)
result.add(matrix[begin][i]);
for (int i = begin + 1; i <= row; i++)
result.add(matrix[i][col]);
for (int i = col - 1; i >= begin; i--)
result.add(matrix[row][i]);
for (int i = row - 1; i > begin; i--)
result.add(matrix[i][begin]);
return 1;
}
public static void main(String[] args) {
Solution test = new Solution();
int[][] a = new int[3][3];
a[0][0] = 1;
a[0][1] = 2;
a[0][2] = 3;
a[1][0] = 4;
a[1][1] = 5;
a[1][2] = 6;
a[2][0] = 7;
a[2][1] = 8;
a[2][2] = 9;
System.out.println(test.spiralOrder(a));
}
}
My test result:
这次题目我的代码运行素的比较慢,估计原因就是因为我设计了子函数,而本质上这道题目是不需要子函数的。所以速度会快很多。但这道题本身没有什么亮点,就这样吧。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return ret;
int width = matrix[0].length;
int height = matrix.length;
int i = 0;
int j = 0;
/** traversal every existed circle */
while (j + width - 1 < matrix[0].length && i + height - 1 < matrix.length) {
traversal(j, i, width, height, matrix, ret);
i++;
j++;
width = width - 2;
height = height - 2;
if (width <= 0 || height <= 0) // if width or height <= 0, quit
break;
}
return ret;
}
/** traverse this circle */
private void traversal(int beginCol, int beginRow, int width, int height, int[][] matrix, ArrayList<Integer> ret) {
for (int i = beginCol; i < beginCol + width; i++)
ret.add(matrix[beginRow][i]);
if (height == 1)
return;
for (int i = beginRow + 1; i < beginRow + height; i++)
ret.add(matrix[i][beginCol + width - 1]);
if (width == 1)
return;
for (int i = beginCol + width - 2; i >= beginCol; i--)
ret.add(matrix[beginRow + height - 1][i]);
for (int i = beginRow + height - 2; i >= beginRow + 1; i--)
ret.add(matrix[i][beginCol]);
}
}
这道题目不难,但是很烦。妈的。。。
感觉第二次写的要简洁一些。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ret = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return ret;
}
int rowBegin = 0;
int rowEnd = matrix.length - 1;
int colBegin = 0;
int colEnd = matrix[0].length - 1;
while (rowBegin <= rowEnd && colBegin <= colEnd) {
for (int i = colBegin; i <= colEnd; i++) {
ret.add(matrix[rowBegin][i]);
}
rowBegin++;
for (int i = rowBegin; i <= rowEnd; i++) {
ret.add(matrix[i][colEnd]);
}
colEnd--;
if (rowBegin <= rowEnd) {
for (int i = colEnd; i >= colBegin; i--) {
ret.add(matrix[rowEnd][i]);
}
rowEnd--;
}
if (colBegin <= colEnd) {
for (int i = rowEnd; i >= rowBegin; i--) {
ret.add(matrix[i][colBegin]);
}
colBegin++;
}
}
return ret;
}
}
第一次知道,恶心的题目得看论坛,都有最优解!
以后每道题目,都看下论坛投票最高的解法。
这个解法就很自然,也容易记住,避免了许多corner case
同时,记住这里,需要判断
if (rowBegin <= rowEnd)
if (colBegin <= colEnd)
参考:
https://discuss.leetcode.com/topic/3713/super-simple-and-easy-to-understand-solution
Anyway, Good luck, Richardo! --- 08/11/2016