[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
一刷我记得用的是12 36 98 74 这种方式，然后往里一层。
遇到长宽是1(比如刚才第二层就剩1个5了)和2([1,2],[3,4])的就只遍历，不往里。但是很麻烦，二刷换了个方法。。
public class Solution
{
public List<Integer> spiralOrder(int[][] matrix)
{
List<Integer> res = new ArrayList<Integer>();
int row = matrix.length;
if(row == 0) return res;
int col = matrix[0].length;
if(col == 0)
{
for(int n = 0; n < row;n++)
{
res.add(matrix[n][0]);
}
return res;
}
helper(0,0,row,col,matrix,res);
return res;
}
public void helper(int currentRow, int currentCol, int rowLeft, int colLeft, int[][] matrix, List<Integer> res)
{
if(rowLeft == 1 && colLeft == 1)
{
res.add(matrix[currentRow][currentCol]);
return;
}
else if(rowLeft == 1)
{
for(int n = 0; n < colLeft;n++)
{
res.add(matrix[currentRow][currentCol]);
currentCol++;
}
return;
}
else if(colLeft == 1)
{
for(int m = 0; m < rowLeft;m++)
{
res.add(matrix[currentRow][currentCol]);
currentRow++;
}
return;
}
else
{
}
if(rowLeft < 1 || colLeft < 1) return;
int tempInt;
for(int m = 0; m < colLeft-1; m++)
{
tempInt = matrix[currentRow][currentCol];
res.add(tempInt);
currentCol++;
}
for(int m = 0; m < rowLeft-1;m++)
{
tempInt = matrix[currentRow][currentCol];
res.add(tempInt);
currentRow++;
}
for(int m = 0; m < colLeft-1; m++)
{
tempInt = matrix[currentRow][currentCol];
res.add(tempInt);
currentCol--;
}
for(int m = 0; m < rowLeft-1;m++)
{
tempInt = matrix[currentRow][currentCol];
res.add(tempInt);
currentRow--;
}
helper(currentRow+1,currentCol+1,rowLeft-2,colLeft-2,matrix,res);
}
}
二刷和一刷相比最大最大的改变是 I changed the name of method helper() to doThisShit(), which sounds more awesome.
public class Solution
{
public List<Integer> spiralOrder(int[][] matrix)
{
List<Integer> res = new ArrayList<Integer>();
if(matrix.length == 0) return res;
/*
A
B C
D
*/
int A = 0;
int B = 0;
int C = matrix[0].length-1;
int D = matrix.length-1;
doThisShit(res,matrix,A,B,C,D);
return res;
}
public void doThisShit(List<Integer> res, int[][] matrix, int A, int B, int C, int D)
{
while(C - B >= 0 && D - A >= 0)
{
for(int i = B; i <= C;i++)res.add(matrix[A][i]);
A++;
for(int i = A; i <= D;i++)res.add(matrix[i][C]);
C--;
for(int i = C; i >= B && D > A-1;i--)res.add(matrix[D][i]);
D--;
for(int i = D; i >= A && B < C+1;i--)res.add(matrix[i][B]);
B++;
}
}
}
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
123 69 87 45 纯绕圈。
特殊情况是长和宽是否相等。
比如123456 会算2次，所以下边和左边要判断是否遍历过了。
1 2 3 4 5 6
A
B C
D
A和D是相等的
上边(A)从1遍历到6，A++;
右边因为A+1超边界，所以不便利，C++;
下边D从6便利到1,D--;(这里反向遍历了654321)
左边因为D-1超边界，所以不遍历，D--；
同理
1
2
3
4
5
会发现B反向遍历了一次5到1.
如果采用8个变量来记录位置，分别记录四个角的X和Y，就没这个问题了，但是这里只用4个，后2个循环需要多加一层判断。