题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵：
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 |
则依次打印出数字
1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
这个题目很有意思，主要考察的是对二维数组的熟悉程度。但如果更加仔细思考，其实它本身是“贪吃蛇”游戏中的碰撞算法，在贪吃蛇游戏中，蛇不能咬住自己的身体，很显然，我们需要使用链表或者队列来存储蛇的身体节点。
解题思路
- 【1】构造 【坐上点】【右上点】【右下点】【左下点】为哨兵点
- 【2】利用LinkedHashMap作为“蛇”的身体，LinkedHashMap是Map，但他本身也是队列，能更好的降低时间复杂度。
- 【3】当数组大小和蛇的身体一样长时停止检索。
- 【4】构造一个Point类用来保存坐标
创建Point类
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public String getKey() {
return x + "-" + y;
}
}
方法实现
public static void printMatrixAsLayer(int[][] arr){
if(arr==null) return;
Map<String,Point> snake = new LinkedHashMap<>();
int ROW = arr.length;
int COL = arr[0].length;
int baseXY = 0; //左上角的起始点 x，y总是相等
int sum = ROW * COL;
while (sum>snake.size()){
int x = baseXY;
int y = baseXY;
while (y<(COL-baseXY)){
Point point = new Point(x, y);
snake.put(point.getKey(),point);
y++;
}
y--;
while (x<(ROW-baseXY)){
Point point = new Point(x, y);
snake.put(point.getKey(),point);
x++;
}
x--;
while (y>=baseXY){
Point point = new Point(x, y);
snake.put(point.getKey(),point);
y--;
}
y++;
while (x>=baseXY){
Point point = new Point(x, y);
snake.put(point.getKey(),point);
x--;
}
x++;
baseXY+=1;
}
for(Map.Entry<String,Point> entry : snake.entrySet()){
Point point = entry.getValue();
System.out.print(arr[point.x][point.y]+" ");
}
}
代码测试
int[][] h1 = {
{01, 02, 03, 04},
{12, 13, 14, 5},
{11, 16, 15, 6},
{10, 9, 8, 07}
};
printMatrixAsLayer(h1);
System.out.println();
int[][] h2 = {
{01, 02, 03, 04},
{05, 06, 07, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
printMatrixAsLayer(h2);
System.out.println();
int[][] h3 = {
{01, 02, 03, 04},
{8, 07, 06, 05}
};
printMatrixAsLayer(h3);
System.out.println();
int[][] h4 = {
{1, 2},
{3, 4},
{5, 6},
{7, 8}
};
printMatrixAsLayer(h4);
输出结果
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
1 2 3 4 5 6 7 8
1 2 4 6 8 7 5 3
