Sunday, April 7, 2013

[LeetCode] Spiral Matrix II, Solution


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 ]
]
» Solve this problem

[Thoughts]
与Spriral Matrix(http://fisherlei.blogspot.com/2013/01/leetcode-spiral-matrix.html)类似,区别在于一个用递归来剥皮,一个用递归来构造。Code可以复用。

[Code]
红色部分为改动部分。可以看出来,与Spriral Matrix的code相比,改动非常小。
1:       vector<vector<int> > generateMatrix(int n) {  
2:            vector<vector<int>> matrix(n);  
3:            for(int i =0; i< n; i++)  
4:            {  
5:                 matrix[i].resize(n);  
6:            }  
7:            generate_order(matrix, 0, n, 0, n, 1);            
8:            return matrix;  
9:       }  
10:       void generate_order(   
11:       vector<vector<int> > &matrix,   
12:       int row_s, int row_len,   
13:       int col_s, int col_len,      
14:       int val)   
15:       {   
16:            if(row_len<=0 || col_len <=0) return;   
17:            if(row_len ==1)   
18:            {   
19:                 for(int i =col_s; i< col_s+col_len; i++)   
20:                     matrix[row_s][i] = val++;       
21:                 return;   
22:            }   
23:            if(col_len ==1)   
24:            {   
25:                 for(int i =row_s; i<row_s + row_len; i++)   
26:                     matrix[i][col_s] = val++;       
27:                 return;   
28:            }   
29:            for(int i =col_s; i<col_s+col_len-1; i++) //up  
30:                 matrix[row_s][i] = val++;   
31:            for(int i =row_s; i<row_s+row_len-1; i++)  //right  
32:                 matrix[i][col_s+col_len-1] = val++;  
33:            for(int i =col_s; i<col_s+col_len-1; i++) //bottom  
34:                 matrix[row_s+row_len-1][2*col_s+ col_len-1 -i] = val++;  
35:            for(int i =row_s; i<row_s+row_len-1; i++) //left  
36:                 matrix[2*row_s+row_len-1-i][col_s] = val++;  
37:            generate_order(matrix, row_s+1, row_len-2, col_s+1, col_len-2, val);   
38:       }  


No comments: