Spiral Matrix

Leave a comment

May 14, 2017 by oneOokay

不写下来我会忘…如何像削苹果皮一样一圈一圈地把一个matrix给剥出一层皮…

需要四个值: rowStart, rowEnd, colStart, colEnd.这四个值在traversal的时候用来限定范围.

一个while loop剥一层: while loop里面的start和end是要取等的,这样才能够取到最中间的奇数元素.

while loop里面四个for-loop分别:

  • 从左到右剥完第一行(所以这里其实剥掉了左右一列的第一个元素)
  • 从上到下剥完除第一行最后一个元素以外的最后一列(这里也剥掉了最后一行到最后一个元素)
  • 从右到左剥完最后一行(这里剥掉了第一列的最后一个元素)
  • 从下到上剥完第一列剩余的元素(第一列的第一个元素在第一个for-loop里面剥完了,第一列的最后一个元素在上一个for-loop里面剥完了)
public List spiralOrder(int[][] matrix) {
        List ans = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return ans;
        int rowStart = 0;
        int rowEnd = matrix.length - 1;
        int colStart = 0;
        int colEnd = matrix[0].length - 1;
//要相等才能够取到奇数行列的最中间的一个数字
while (rowStart <= rowEnd && colStart <= colEnd){ 
//从左到右剥第一行
 for (int i = colStart; i <= colEnd; i ++){
 ans.add(matrix[rowStart][i]);
 }
 rowStart ++;//第一行完全走完了,所以rowStart ++
//从上到下剥最后一列
 for (int i = rowStart; i <= rowEnd; i ++){
 ans.add(matrix[i][colEnd]); 
 }
 colEnd --;//最后一列完全走完了,所以colEnd --
 //这里要在最后一行从后往前走,因为之前的rowStart被update了,
//所以要check rowEnd是否还是valid的
 if(rowEnd >= rowStart){
//从右到左剥最后一行
 for (int i = colEnd; i >= colStart; i --){
 ans.add(matrix[rowEnd][i]);
 }
 rowEnd --;//最后一行剥完了,rowEnd --
 }
 //这里要在第一列从下往上走,colEnd被update了
//所以要check colStart是否还是valid的
 if(colStart <= colEnd){
 for (int i = rowEnd; i >= rowStart; i --){
 ans.add(matrix[i][colStart]);
 }
 colStart ++;//剥完了第一列,colStart ++
 }
 }
        return ans;
    }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: