kiddy

Spiral Matrix

leave a comment »

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].

class Solution {
public:
    
    void spiralRec(vector<vector<int> > &matrix, int rowInd, int colInd, int rowNum, int colNum, vector<int> &ret){
        if(colNum <=0 || rowNum <= 0)   return;
        int j = 0;
        for(; j < colNum; j++){
            ret.push_back(matrix[rowInd][colInd+j]);
        }
        int i = 1;
        for(; i < rowNum-1; i++){
            ret.push_back(matrix[rowInd+i][colInd+colNum-1]);
        }
        if(rowNum>=2){
            j--;
            for(; j >= 0; j--){
                ret.push_back(matrix[rowInd+rowNum-1][colInd+j]);
            }    
        }
        if(colNum >= 2){
            i--;
            for(; i >= 1; i--){
                ret.push_back(matrix[rowInd+i][colInd]);
            }    
        }        
        spiralRec(matrix, rowInd+1, colInd+1, rowNum-2, colNum-2, ret);
    }
    
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> ret;
        ret.clear();
        int rowNum = matrix.size();
        if(rowNum == 0) return ret;
        int colNum = matrix[0].size();
        spiralRec(matrix, 0, 0, rowNum, colNum, ret);
        return ret;
    }
};

Question 2: Spiral Matrix II

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 ]
]
class Solution {
public:

    void spRec(vector<vector<int> > &ret, int rowNum, int colNum, int beginRow, int beginCol, int &cur){
        if(rowNum == 0 || colNum == 0)  return;
        if(rowNum == 1){
            ret[beginRow][beginCol] = cur;
        }
        else{
            for(int j = 0; j < colNum; j++){
                ret[beginRow][beginCol+j] = cur++;
            }
            for(int i = 1; i < rowNum-1; i++){
                ret[beginRow+i][beginCol+colNum-1] = cur++;
            }
            for(int j = colNum-1; j >= 0; j--){
                ret[beginRow+rowNum-1][beginCol+j] = cur++;
            }
            for(int i = rowNum-2; i > 0; i--){
                ret[beginRow+i][beginCol] = cur++;
            }
        }
        if(rowNum-2 >= 0 && colNum-2 >= 0) {
            spRec(ret, rowNum-2, colNum-2, beginRow+1, beginCol+1, cur);
        }
    }

    vector<vector<int> > generateMatrix(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ret(n, vector<int>(n,0));
        int rowNum = n;
        int colNum = n;
        int cur = 1;
        spRec(ret, rowNum, colNum, 0, 0, cur);
        return ret;        
    }
};
Advertisements

Written by linzhongzl

April 29, 2013 at 9:42 pm

Posted in Leetcode

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: