文档章节

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

悠悠然然
 悠悠然然
发布于 2015/04/04 12:03
字数 1658
阅读 3038
收藏 117

螺旋矩阵和蛇型矩阵,是两个比较有趣的矩阵,有许多的公司面试题中有出现,这两个题的答案也有许多种,简单问一下度娘,就各自有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;
            }
这里就是上面说的逻辑的实现。

嗯嗯,这里的判断多了些,暂时没有想到如何进行优化,哪位同学出手优化一下?

总结

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

以前做过ThoughtWorks代码挑战——FizzBuzzWhizz游戏,见悠然乱弹:拉钩网FizzBuzzWhizz试题之悠然版解答

结果在过去大半年的了,接到他们HR电话,说是问我对他们的程序员职位是不是感兴趣,偶幽然滴回答:偶热切的等了你半年,可惜你没有来找我,最后不得己加入OSChina了,然后才发现OSChina才是偶滴真爱......

© 著作权归作者所有

悠悠然然

悠悠然然

粉丝 2475
博文 185
码字总数 363071
作品 14
杭州
架构师
私信 提问
加载中

评论(17)

g
goodjin
思路不错,赞一个。也可以考虑用递归来做13
悠悠然然
悠悠然然 博主

引用来自“rover0913”的评论

不用数组,也可以直接输出螺旋矩阵
http://www.oschina.net/code/snippet_98254_38936
一个题有多种解法的,算法的是最简单的。这里其实主要是体现编写者对循环和判断语句的掌控情况的。
悠悠然然
悠悠然然 博主

引用来自“NEVER堕落”的评论

思路很好啊 赞~
看懂就好,看不懂就不好,呵呵
悠悠然然
悠悠然然 博主

引用来自“北风刮的不认真了”的评论

太赞了
谢谢支持
悠悠然然
悠悠然然 博主

引用来自“德胜”的评论

https://github.com/haogrgr/haogrgr-test/blob/master/src/main/java/com/haogrgr/test/algorithm/PrintSpiralMatrix.java

偶以前也写过一个,花了n久

引用来自“北风刮的不认真了”的评论

对比下两个版本。。。。我竟然不知道说什么
其实,他的版本和我的版本主体思路是一样的,只是细节上和函数划分上有点不同。当然如果行走的处理技巧上,也有一点细微差别。整体来看,也是相当不错的实现。
北风刮的不认真了
北风刮的不认真了
太赞了
北风刮的不认真了
北风刮的不认真了

引用来自“德胜”的评论

https://github.com/haogrgr/haogrgr-test/blob/master/src/main/java/com/haogrgr/test/algorithm/PrintSpiralMatrix.java

偶以前也写过一个,花了n久
对比下两个版本。。。。我竟然不知道说什么
NEVER堕落
NEVER堕落
思路很好啊 赞~
悠悠然然
悠悠然然 博主

引用来自“quarryman”的评论

很优雅,学习了
呵呵,互相学习。
悠悠然然
悠悠然然 博主

引用来自“純白陰影”的评论

你是红薯的人?
呵呵,人不是@红薯 的,心是了。
现金奖励:挑战编程极限的问题

今天我想挑战一下OSCHINA的亲们的编程能力,出一道百度、谷歌不到答案的问题,第一个挑战成功的,直接奖励现金100元RMB(本人也是苦B码农,纯属意思一下)。 以前发过一条循环语句打印螺旋矩...

悠悠然然
2015/08/14
4.7K
67
OSChina 技术周刊第二十八期 —— 用 React 编写移动应用

每周技术抢先看,总有你想要的! 移动开发 【软件】RichEditor for Android 【软件】用 React 编写移动应用 React Native 【软件】iOS 图表控件 ios-charts 【博客】iOS 越狱开发——如何将应...

OSC编辑部
2015/04/05
1K
0
OSChina 技术周刊第二十八期 —— 每周技术精粹

每周技术抢先看,总有你想要的! 移动开发 【软件】RichEditor for Android 【软件】用 React 编写移动应用 React Native 【软件】iOS 图表控件 ios-charts 【博客】【iOS越狱开发】如何将应...

OSC编辑部
2015/04/05
298
0
悠然乱弹:挑战编程极限的问题终于有解了

问题的来历 在群里面一个小萝莉非要说拜我为师,呵呵,对于程序媛我一向--嗯嗯觉得程序不如人好看,再加上该名萝莉大学还没毕业,术语都多半没有听过,于是就想着拒绝,当时嘴一贱,就说了一...

悠悠然然
2015/08/17
2.7K
36
求螺旋矩阵指定坐标的值

螺旋矩阵定义:螺旋矩阵是指一个呈螺旋状的矩阵,它的数字由第一行开始到右边不断变大,向下变大,向左变大,向上变大,如此循环。 坐标(4,3)对应的数字为34。 请定义一个函数,输入n,x,...

FrankNie0101
2017/09/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

快速排序与冒泡排序

快速排序与冒泡排序 比较基础,特准备写博客记录和思考一下

T型人才追梦者
48分钟前
3
0
OSChina 周三乱弹 —— 调查人员问狗 那你在做什么啊?

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 小小编辑推荐:《Let It Be》- John Denver 《Let It Be》- John Denver 手机党少年们想听歌,请使劲儿戳(这里) @FalconChen :每天看一遍,...

小小编辑
今天
7
0
高效程序员的45个习惯总结版-文末脑图

1 做事 一个重大的错误应该被当做一次学习而不是指责他人的机会,团队成员一起工作,应该互相帮助,而不是互相指责 2 欲速则不达 不要为了修复问题而去修复,要投入时间和精力保持代码整洁 ...

阿提说说
今天
18
0
带南海九段线分位数地图可视化(R语言版)

今天带来一篇承诺虾神的可视化博客。内容是使用R语言进行带南海九段线分位数地图可视化。虾神的原博文地址如下(Python版)。 Python实现带南海九段线分位数地图完整可视化版本(附代码及数据...

胖胖雕
今天
12
0
Nginx 的进程结构,你明白吗?

Nginx 进程结构 这篇文章我们来看下 Nginx 的进程结构,Nginx 其实有两种进程结构: 单进程结构 多进程结构 单进程结构实际上不适用于生产环境,只适合我们做开发调试使用。因为在生产环境中...

武培轩
今天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部