Tuesday, October 15, 2013

Spiral Matrix II [Leetcode]

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 ]
] 
Solution: generate the matrix layer by layer from outside to inside.
class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(n<=0){
            vector<vector<int> > r;
            return r;
        }
        vector<vector<int> > ret(n, vector<int>(n, 0));
        int val = 0;
        for(int i=0; i<n/2; i++){
            int size = n-2*i;
            //top
            for(int j=0; j<size; j++)
                ret[i][i+j]=(++val);
            //right
            for(int j=0; j<size-2; j++)
                ret[i+1+j][i+size-1]=(++val);
            //bottom
            for(int j=0; j<size; j++)
                ret[i+size-1][i+size-1-j] =(++val);
            //left
            for(int j=0; j<size-2; j++)
                ret[i+size-2-j][i]=(++val);
        }
        if(n%2==1)
            ret[n/2][n/2] = n*n;
        return ret;
    }
};

No comments:

Post a Comment