1+ package Algorithms .array ;
2+
3+ public class GenerateMatrix1 {
4+ public int [][]generateMatrix1 (int n ) {
5+ int [][]ret =new int [n ][n ];
6+
7+ if (n ==0 ) {
8+ // return a [] not a NULL.
9+ return ret ;
10+ }
11+
12+ int number =0 ;
13+ int rows =n ;
14+
15+ int x1 =0 ;
16+ int y1 =0 ;
17+
18+ while (rows >0 ) {
19+ int x2 =x1 +rows -1 ;
20+ int y2 =y1 +rows -1 ;
21+
22+ // the Whole first row.
23+ for (int i =y1 ;i <=y2 ;i ++) {
24+ number ++;
25+ ret [x1 ][i ] =number ;
26+ }
27+
28+ // the right column except the first and last line.
29+ for (int i =x1 +1 ;i <x2 ;i ++) {
30+ number ++;
31+ ret [i ][y2 ] =number ;
32+ }
33+
34+ // This line is very important.
35+ if (rows <=1 ) {
36+ break ;
37+ }
38+
39+ // the WHOLE last row.
40+ for (int i =y2 ;i >=y1 ;i --) {
41+ number ++;
42+ ret [x2 ][i ] =number ;
43+ }
44+
45+ // the left column. column keep stable
46+ // x: x2-1 --> x1 + 1
47+ for (int i =x2 -1 ;i >x1 ;i --) {
48+ number ++;
49+ ret [i ][y1 ] =number ;
50+ }
51+
52+ // remember this.
53+ rows -=2 ;
54+ x1 ++;
55+ y1 ++;
56+ }
57+
58+ return ret ;
59+ }
60+
61+ /*
62+ Solution 2: use direction.
63+ */
64+ public int [][]generateMatrix2 (int n ) {
65+ int [][]ret =new int [n ][n ];
66+ if (n ==0 ) {
67+ return ret ;
68+ }
69+
70+ int []x = {1 ,0 , -1 ,0 };
71+ int []y = {0 ,1 ,0 , -1 };
72+
73+ int num =0 ;
74+
75+ int step =0 ;
76+ int candElements =0 ;
77+
78+ int visitedRows =0 ;
79+ int visitedCols =0 ;
80+
81+ // 0: right, 1: down, 2: left, 3: up.
82+ int direct =0 ;
83+
84+ int startx =0 ;
85+ int starty =0 ;
86+
87+ while (true ) {
88+ if (x [direct ] ==0 ) {
89+ // visit the Y axis
90+ candElements =n -visitedRows ;
91+ }else {
92+ // visit the X axis
93+ candElements =n -visitedCols ;
94+ }
95+
96+ if (candElements <=0 ) {
97+ break ;
98+ }
99+
100+ // set the cell.
101+ ret [startx ][starty ] = ++num ;
102+ step ++;
103+
104+ // change the direction.
105+ if (step ==candElements ) {
106+ step =0 ;
107+ visitedRows +=x [direct ] ==0 ?0 :1 ;
108+ visitedCols +=y [direct ] ==0 ?0 :1 ;
109+
110+ // change the direction.
111+ direct = (direct +1 ) %4 ;
112+ }
113+
114+ startx +=y [direct ];
115+ starty +=x [direct ];
116+ }
117+
118+ return ret ;
119+ }
120+
121+ /*
122+ Solution 3: 使用四条bound来限制的方法.
123+ */
124+ public int [][]generateMatrix (int n ) {
125+ int [][]ret =new int [n ][n ];
126+ if (n ==0 ) {
127+ return ret ;
128+ }
129+
130+ int top =0 ,bottom =n -1 ,left =0 ,right =n -1 ;
131+ int num =1 ;
132+ while (top <=bottom ) {
133+ if (top ==bottom ) {
134+ ret [top ][top ] =num ++;
135+ break ;
136+ }
137+
138+ // first line.
139+ for (int i =left ;i <right ;i ++) {
140+ ret [top ][i ] =num ++;
141+ }
142+
143+ // right line;
144+ for (int i =top ;i <bottom ;i ++) {
145+ ret [i ][right ] =num ++;
146+ }
147+
148+ // bottom line;
149+ for (int i =right ;i >left ;i --) {
150+ ret [bottom ][i ] =num ++;
151+ }
152+
153+ // left line;
154+ for (int i =bottom ;i >top ;i --) {
155+ ret [i ][left ] =num ++;
156+ }
157+
158+ top ++;
159+ bottom --;
160+ left ++;
161+ right --;
162+ }
163+
164+ return ret ;
165+ }
166+ }