Monday, June 23, 2014

Leetcode - Spiral Matrix && Spiral Matrix II

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].
[Thoughts]: I 和II的思路一样, 注意下循环结束点,若行或列数为基数,最后一层可能为一行或一列,特殊处理下。
public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        int row = matrix.length;
        int col = row==0 ? 0 : matrix[0].length;
        
        int x=0, y=0; 
        while(row>0 && col>0){
            if(row==1){
                for(int i=0; i<col; i++)
                    res.add(matrix[x][y++]);
                return res;
            }
            
            if(col==1){
                for(int i=0; i<row; i++)
                    res.add(matrix[x++][y]);
                return res;
            }
            for(int i=0; i<col-1; i++)
                res.add(matrix[x][y++]); //at the end y==col-1
            for(int i=0; i<row-1; i++)
                res.add(matrix[x++][y]);//at the end x==row-1
            for(int i=col-1; i>0; i--)
                res.add(matrix[x][y--]);
            for(int i=row-1; i>0; i--)
                res.add(matrix[x--][y]);
                
            x++;
            y++;
            row -= 2;
            col -= 2;
        }
        return res;
    }
}

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

[Thoughts]: 设一个val,一层一层走, val值也跟着滚动
public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int row = n;
        int col = n;
        
        int x=0, y=0, val =1;
        
        while(row>0 && col>0){
            if(row==1){
                for(int i=0; i<col; i++)
                    matrix[x][y++]=val++;
                return matrix;
            }
            if(col==1){
                for(int i=0; i<row; i++)
                    matrix[x++][y]=val++;
                return matrix;
            }
            for(int i=0; i<col-1; i++)
                matrix[x][y++]=val++;//at the end of loop, y = col-1
            for(int i=0; i<row-1; i++)
                matrix[x++][y] = val++; // at the end of loop, x = row-1;
            for(int i= col-1; i>0; i--)
                matrix[x][y--] = val++; //at the end of loop, y=0;
            for(int i=row-1; i>0; i--)
                matrix[x--][y]= val++;
            
            x   = x + 1;
            y   = y + 1;
            row = row - 2;
            col = col - 2;
            
        }
        
        return matrix;
        
    }
}

No comments:

Post a Comment