摘要 螺旋矩阵和蛇型矩阵,是两个比较有趣的矩阵,有许多的公司面试题中有出现,这两个题的答案也有许多种,简单问一下度娘,就各自有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,让我们一起动手,了解框架的奥秘!
相关推荐
对话框乱弹的小程序,点击开始后会不停弹300个大小不等位置不确定的对话框,伴随windows的一些报警声,很有节奏的感觉。
自定义View实现Android快速索引,模仿微信的通讯录效果。右侧的快速索引条按下时候没有变成灰色,但是我设置了selector,不知道为什么没有生效,请知道原因的朋友告诉我一下,感激了。
《自己动手写前端框架》电子书.pdf 1. Tiny框架 2. 算法感想 3. 悠然乱弹 4. 未分类
使用fiddler工具进行抓包,使用python进行osc乱弹抢沙发
into沙龙第期康国庆乱弹传统企业转型以及与互联网结合的方式PPT教案.pptx
《浅析新媒介生态环境下广播娱乐节目的编辑特征——以FM101.1西安乱弹“刘翔来了”为例》.zip
《浅析新媒介生态环境下广播娱乐节目的编辑特征——以FM101.1西安乱弹“刘翔来了”为例》.doc
《浅析新媒介生态环境下广播娱乐节目的编辑特征——以FM101.1西安乱弹“刘翔来了”为例》-论文.zip
经历了数月艰苦的开放和程序员最痛苦的测试,今天,世上最强,最完善,最稳定和测试最充分,文档最完整的旗舰版和平之翼Java通用代码生成器SMEU 3.2.0 正式版乌篷船盛装发布了。欢迎大家下载使用。 请至本项目码云...
修复单类代码生成器4个问题。 2.新增创建加载数据库时,表名过滤功能。 3.表名生成命名规则,字符串替换功能。 4.模板中字段排序方法公开。 5.字段默认值函数的处理。 6.导出的sql脚本中,单引号 '的问题。...
Ajax是一种已不是加载脚本,其最古老的实现方式是利用iframe来加载远程的脚本利用top.Function来调用父窗体的方法。利用a等HTML的target属性来指定。简单但是后期维护复杂化了并且在跨越方面很麻烦。接着就...
利用GestureDetector实现页面滑动Demo
京剧之名始建于清光绪二年(1876年)的申报,历史上曾有皮黄、二黄、黄腔、京调、京戏、平剧、国剧等称谓,清朝乾隆五十五年(1790年)四大徽班(三庆、四喜、春台、和春)四班进京后与京剧坛的昆曲、汉剧、乱弹等...
本文由林氏原创,遵循GPL许可,你可以自由地对本文进行任何目的的修改、转载、引用和发布,但基于此文所作的任何修改、转载、引用和发布品也需要遵循GPL许可,并要求在开头保留本声明。 联系作者:如果您有什么样的...
第1章 设计的数据和分析 1 看不懂数据 2 不配看数据 2 为了看数据而看数据 2 不去筛选数据 3 不关注数据采集的方式和方法 4 只用定量数据,没有定性数据 5 设计中的数据分析 5 数据——判断淘宝店铺页面设计优劣的...
android每个应用都有欢迎页面和引导页,这个小Demo可以达到一个可扩展的效果。
技术乱弹之hive源码之词法语法解析(MD版格式已乱 请查看docx版) 第一章 前言 我们知道 hive是一个基于hadoop上面提供了类sql的接口的组件,以方便熟悉sql的人使用hadoop,对大数据的处理。限于精力,本文...
常见问题乱弹 A.1. 怎么查看ext2里的api文档 A.2. 想把弹出对话框单独拿出来用的看这里 A.3. 想把日期选择框单独拿出来用的看这里 B. 修改日志 C. 后记 C.1. 2007年12月5日,迷茫阶段 C.1.1. 仇恨 C.1.2...