螺旋矩阵和蛇型矩阵,是两个比较有趣的矩阵,有许多的公司面试题中有出现,这两个题的答案也有许多种,简单问一下度娘,就各自有N种实现,来源也非常丰富,比如CSDN、ITEYE、等等,当然也包括著名的OSC,但是整体看下来,呵呵,比较顺眼的比较少,比较经典的就越发少了。
考虑到不同的语言有不同的语言特性,因此今天就只用Java来进行实现,看看螺旋矩阵和蛇型矩阵的悠然版实现,让我们的OSC也更加高大上一些,。
概念说明
什么是螺旋矩阵
螺旋矩阵是指一个呈螺旋状的矩阵,它的数字由第一行开始到右边不断变大,向下变大,
向左变大,向上变大,如此循环。
下面是几个螺旋矩阵的示例:
下面是1阶螺旋矩阵:
1下面是2阶螺旋矩阵:
1 24 3
下面是3阶螺旋矩阵:
1 2 38 9 4
7 6 5
下面是4阶螺旋矩阵:
1 2 3 412 13 14 5
11 16 15 6
10 9 8 7
下面是5阶螺旋矩阵:
1 2 3 4 516 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
什么是蛇型矩阵
这个东东说起来比较抽象,玩过贪吃蛇么?如果玩过大致就可以理解了。
下面看看实际示例
下面是1阶蛇形矩阵:
1下面是2阶蛇形矩阵:
1 32 4
下面是3阶蛇形矩阵:
1 3 42 5 8
6 7 9
下面是4阶蛇形矩阵:
1 3 4 102 5 9 11
6 8 12 15
7 13 14 16
下面是5阶蛇形矩阵:
1 3 4 10 112 5 9 12 19
6 8 13 18 20
7 14 17 21 24
15 16 22 23 25
悠然版解法
螺旋矩阵
分析
简单看看螺旋矩阵,其规律就是一圈一圈的往里绕,因此我们可以想象有一条贪吃蛇,它很听话,如果要出格子或者碰到格子里有数的时候就向右转一下,然后在它路过的格子里顺序填充上数字就好
代码
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
|
public class SpiralMatrix {
public static int [][] spiralMatrix( int n) {
int spiralMatrix[][] = new int [n][n];
for ( int num = 1 , x = 0 , y = 0 , xDir = 1 , yDir = 0 ; num <= n * n; num++) {
spiralMatrix[x][y] = num;
if (x + xDir < 0 || y + yDir < 0 || x + xDir == n || y + yDir == n || spiralMatrix[x + xDir][y + yDir] != 0 ) { //如果到边界了就换方向
if (xDir != 0 ) {
yDir = xDir;
xDir = 0 ;
} else {
xDir = -yDir;
yDir = 0 ;
}
}
x += xDir;
y += yDir;
}
return spiralMatrix;
}
public static void main(String[] args) {
for ( int num = 1 ; num < 6 ; num++) {
int [][] result = spiralMatrix(num);
System.out.printf( "下面是%s阶螺旋矩阵:\n" ,num);
for ( int i = 0 ; i < num; i++) {
for ( int j = 0 ; j < num; j++) {
System.out.printf( "%3s " , result[j][i]);
}
System.out.println();
}
}
}
} |
1
|
for ( int num = 1 , x = 0 , y = 0 , xDir = 1 , yDir = 0 ; num <= n * n; num++)
|
x,y为贪吃蛇要走过的位置,默认从左上角走起;
xDir和yDir为行进的方向,默认是水平向右走。
1
|
if (x + xDir < 0 || y + yDir < 0 || x + xDir == n || y + yDir == n || spiralMatrix[x + xDir][y + yDir] != 0 )
|
1
2
3
4
5
6
7
|
if (xDir != 0 ) {
yDir = xDir;
xDir = 0 ;
} else {
xDir = -yDir;
yDir = 0 ;
}
|
当然,如果没有碰到边界也没有碰到前面格子有数字,那就不调整方向,让它继续走,如下。
1
2
|
x += xDir;
y += yDir;
|
然后,就没有然后了,然后贪吃蛇同学就帮我们完成了任务,来一个大点的看看?
1
2
3
4
5
6
7
8
|
1 2 3 4 5 6 7 8 28 29 30 31 32 33 34 9
27 48 49 50 51 52 35 10
26 47 60 61 62 53 36 11
25 46 59 64 63 54 37 12
24 45 58 57 56 55 38 13
23 44 43 42 41 40 39 14
22 21 20 19 18 17 16 15
|
蛇形矩阵
分析
简单看看蛇形矩阵,它的规律也很简单,只不过是如何走的规律变了一些,总结一下就是:贪吃蛇总是斜着走的,如果要走出边界,那么就换个方向走,只不过要走出左边时,就向下移动一个格子走;要走出上边时,就向右移动一个格子走;要走出下边格子时,就向右移动一个格子走,要走出右边格子时,就向下移动一个格子走;如果没有走出格子,就延着原来的方向走。
代码
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
34
35
36
37
|
public class SnakeMatrix {
public static int [][] snakeMatrix( int n) {
int snakeMatrix[][] = new int [n][n];
for ( int num = 1 , x = 0 , y = 0 , xDir = - 1 , yDir = 1 ; num <= n * n; num++) {
snakeMatrix[x][y] = num;
if (x + xDir == n) {
y += xDir;
} else if (y + yDir == n) {
x += yDir;
} else if (x + xDir < 0 ) {
y += yDir;
} else if (y + yDir < 0 ) {
x += xDir;
} else { //其它情况保持原有方向前行
x += xDir;
y += yDir;
continue ;
}
xDir = -xDir;
yDir = -yDir;
}
return snakeMatrix;
}
public static void main(String[] args) {
for ( int num = 1 ; num < 6 ; num++) {
int [][] result = snakeMatrix(num);
System.out.printf( "下面是%s阶蛇形矩阵:\n" , num);
for ( int i = 0 ; i < num; i++) {
for ( int j = 0 ; j < num; j++) {
System.out.printf( "%3s " , result[j][i]);
}
System.out.println();
}
}
}
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
|
if (x + xDir == n) {
y += xDir;
} else if (y + yDir == n) {
x += yDir;
} else if (x + xDir < 0 ) {
y += yDir;
} else if (y + yDir < 0 ) {
x += xDir;
} else { //其它正常转向
x += xDir;
y += yDir;
continue ;
}
|
嗯嗯,这里的判断多了些,暂时没有想到如何进行优化,哪位同学出手优化一下?
总结
自此,悠然版螺旋矩阵和蛇形矩阵就完成了。
以前做过ThoughtWorks代码挑战——FizzBuzzWhizz游戏,见悠然乱弹:拉钩网FizzBuzzWhizz试题之悠然版解答
结果在过去大半年的了,接到他们HR电话,说是问我对他们的程序员职位是不是感兴趣,偶幽然滴回答:偶热切的等了你半年,可惜你没有来找我,最后不得己加入OSChina了,然后才发现OSChina才是偶滴真爱......