悠然乱弹：螺旋矩阵和蛇型矩阵的悠然版实现

摘要 螺旋矩阵和蛇型矩阵，是两个比较有趣的矩阵，有许多的公司面试题中有出现，这两个题的答案也有许多种，简单问一下度娘，就各自有N种实现，但是整个看下来，呵呵，比较顺眼的比较少。 考虑到不同的语言有不同的语言特性，因此今天就只用Java来进行实现，看看螺旋矩阵和蛇型矩阵的悠然版实现。

 

螺旋矩阵和蛇型矩阵，是两个比较有趣的矩阵，有许多的公司面试题中有出现，这两个题的答案也有许多种，简单问一下度娘，就各自有N种实现，来源也非常丰富，比如CSDN、ITEYE、等等，当然也包括著名的OSC，但是整体看下来，呵呵，比较顺眼的比较少，比较经典的就越发少了。

考虑到不同的语言有不同的语言特性，因此今天就只用Java来进行实现，看看螺旋矩阵和蛇型矩阵的悠然版实现，让我们的OSC也更加高大上一些，。

 

概念说明

什么是螺旋矩阵

 

螺旋矩阵是指一个呈螺旋状的矩阵，它的数字由第一行开始到右边不断变大，向下变大，
向左变大，向上变大，如此循环。

下面是几个螺旋矩阵的示例：

下面是1阶螺旋矩阵:

  1 
下面是2阶螺旋矩阵:

  1   2 
  4   3 
下面是3阶螺旋矩阵:

  1   2   3 
  8   9   4 
  7   6   5 
下面是4阶螺旋矩阵:

  1   2   3   4 
 12  13  14   5 
 11  16  15   6 
 10   9   8   7 
下面是5阶螺旋矩阵:

  1   2   3   4   5 
 16  17  18  19   6 
 15  24  25  20   7 
 14  23  22  21   8 
 13  12  11  10   9

什么是蛇型矩阵

 

这个东东说起来比较抽象，玩过贪吃蛇么？如果玩过大致就可以理解了。

下面看看实际示例

下面是1阶蛇形矩阵:

  1 
下面是2阶蛇形矩阵:

  1   3 
  2   4 
下面是3阶蛇形矩阵:

  1   3   4 
  2   5   8 
  6   7   9 
下面是4阶蛇形矩阵:

  1   3   4  10 
  2   5   9  11 
  6   8  12  15 
  7  13  14  16 
下面是5阶蛇形矩阵:

  1   3   4  10  11 
  2   5   9  12  19 
  6   8  13  18  20 
  7  14  17  21  24 
 15  16  22  23  25 

悠然版解法

螺旋矩阵

 

分析

简单看看螺旋矩阵，其规律就是一圈一圈的往里绕，因此我们可以想象有一条贪吃蛇，它很听话，如果要出格子或者碰到格子里有数的时候就向右转一下，然后在它路过的格子里顺序填充上数字就好

 

代码

 

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();
            }
        }
    }
}

 

说明

 

for (int num = 1, x = 0, y = 0, xDir = 1, yDir = 0; num <= n * n; num++)

 这里其实很简单，只是为了省点代码行数，因此把一些变量声明放这里了，实际放在外面更合适。
x,y为贪吃蛇要走过的位置，默认从左上角走起；

xDir和yDir为行进的方向，默认是水平向右走。

if (x + xDir < 0 || y + yDir < 0 || x + xDir == n || y + yDir == n || spiralMatrix[x + xDir][y + yDir] != 0)

 这里的意思是，如果要出边界（一共有4个边界），或者碰到前面的格子中有数字的时候就调整一下方便。

                if (xDir != 0) {
                    yDir = xDir;
                    xDir = 0;
                } else {
                    xDir = -yDir;
                    yDir = 0;
                }

 当然，如果没有碰到边界也没有碰到前面格子有数字，那就不调整方向，让它继续走，如下。

            x += xDir;
            y += yDir;

 然后，就没有然后了，然后贪吃蛇同学就帮我们完成了任务，来一个大点的看看？

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

 

蛇形矩阵

 

分析

简单看看蛇形矩阵，它的规律也很简单，只不过是如何走的规律变了一些，总结一下就是：贪吃蛇总是斜着走的，如果要走出边界，那么就换个方向走，只不过要走出左边时，就向下移动一个格子走；要走出上边时，就向右移动一个格子走；要走出下边格子时，就向右移动一个格子走，要走出右边格子时，就向下移动一个格子走；如果没有走出格子，就延着原来的方向走。

 

代码

 

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();
            }
        }
    }
}

 

说明

 

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;
            }

 这里就是上面说的逻辑的实现。
嗯嗯，这里的判断多了些，暂时没有想到如何进行优化，哪位同学出手优化一下？

 

总结

自此，悠然版螺旋矩阵和蛇形矩阵就完成了。

欢迎登录关注：http://bbs.tinygroup.org，本例涉及的代码和框架资料，将会在论坛分享。技术交流群：228977971，让我们一起动手，了解框架的奥秘！