Sunday, November 23, 2014

[LeetCode] Spiral Matrix I, II

Spiral Matrix I
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].

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

思路:Spiral Matrix I

与Rotate Image那题类似,一层一层处理。但这题有两个注意点:
1. m和n可以不同,所以对于第i层来说,最后一行为lastRow = m-1-i,而最后一列为lastCol = n-1-i。所以层数由min(m,n)决定。
2. 当min(m,n)为奇数时,最后一层为一行或一列,需要特殊处理。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> ret;
        if(matrix.empty() || matrix[0].empty()) return ret;
        int m = matrix.size(), n = matrix[0].size();
        int nlvl = (min(m,n)+1)/2;
        for(int i=0; i<nlvl; i++) {
            int lastRow = m-1-i;
            int lastCol = n-1-i;
            if(lastRow==i) {    // one row remain
                for(int j=i; j<=lastCol; j++)
                    ret.push_back(matrix[i][j]);
            }
            else if(lastCol==i) {   // one col remain
                for(int j=i; j<=lastRow; j++)
                    ret.push_back(matrix[j][i]);
            }   
            else {
                for(int j=i; j<lastCol; j++) 
                    ret.push_back(matrix[i][j]);
                for(int j=i; j<lastRow; j++)
                    ret.push_back(matrix[j][lastCol]);
                for(int j=lastCol; j>i; j--)
                    ret.push_back(matrix[lastRow][j]);
                for(int j=lastRow; j>i; j--)
                    ret.push_back(matrix[j][i]);
            }
        }
        return ret;
        
    }
};


思路:Spiral Matrix II

II比I简单,一样的按层访问法。由于是正方形矩阵,当n为奇数时,最后只会剩下一个数字即matrix[n/2][n/2],最后不要忘记补填上这个数字。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        vector<vector<int>> ret(n,vector<int>(n,0));
        int nlvl = n/2;
        int val = 1;
        for(int i=0; i<nlvl; i++) {
            int last = n-1-i;
            for(int j=i; j<last; j++) 
                ret[i][j] = val++;
            for(int j=i; j<last; j++)
                ret[j][last] = val++;
            for(int j=last; j>i; j--)
                ret[last][j] = val++;
            for(int j=last; j>i; j--)
                ret[j][i] = val++;
        }
        if(n%2==1) ret[n/2][n/2] = val;
        return ret;
    }
};

No comments:

Post a Comment