首页 > 代码库 > java下蛇形回环矩阵的实现

java下蛇形回环矩阵的实现

前文废话:这个问题据说是腾讯之前的一道笔试题,由于当时没认真看,现在记不清这种矩阵是不是叫“蛇形回环矩阵”......请大家直接看图1,就是那个样子的矩阵。

问题描述:输入一个N,实现N×N的蛇形回环矩阵(即图1类型)

技术分享

(N=5时的蛇形回环矩阵)

我们先把N为奇数和N为偶数的情况分开。先来看N=3、5、7时的该类矩阵是什么情况:

技术分享      技术分享        技术分享

看上去彼此之间并无规律,对这道题最简单粗暴的解法似乎就是构建一个二维数组,然后按人的正常思维向里填数字构建。

但是——如果用(最大数+1)减去每个数,那么这三个矩阵就变成了:

技术分享              技术分享   技术分享

现在就有了规律。

而N为偶数时,彼此之间也是这样的规律。

所以只要得到N=K-2时的矩阵,就能通过在原先的每行前添一列,后面添一列,然后上面添一行,下面添一行,就可以了。

为了实现这个能在前面插入的功能,构建二维的ArrayList。

实现的函数代码如下:

 1 //判断N是偶数还是奇数,N为偶数时num=count,为奇数时num = count-1  
 2     public static void getArray(int num,int count){
 3         ArrayList<ArrayList> listAll = new ArrayList<ArrayList>(count);//二维Arraylist
 4         if(num != count){//奇数时先构建最核心的1
 5             ArrayList start = new ArrayList(count);
 6             start.add(1);
 7             listAll.add(start);
 8         }
 9         for(int i=0;i<num/2;i++){
10             ArrayList listHead = new ArrayList();//构建要加的第一行
11             ArrayList listEnd = new ArrayList();//构建要加的最末行
12             int k;
13             if(num !=count)
14                 k = 2*i+3;
15             else
16                 k = 2*i+2;
17             for(int j=0;j<k;j++){
18                 listHead.add(k*k-j);//填充要加的第一行
19                 listEnd.add((k-2)*(k-2)+k-1+j);//填充要加的最末行
20                 if(j<(k-2)){//原有的每行加头加尾
21                     ArrayList listTem = new ArrayList();
22                     listTem = listAll.get(j);
23                     listTem.add(0,(k-2)*(k-2)+1+j);
24                     listTem.add(k*k-k-j);
25                     listAll.set(j,listTem);
26                 }
27             }
28             listAll.add(0,listHead);//加入第一行
29             listAll.add(listEnd);//加入最末行
30         }
31 //输出
32         for(int i=0;i<count;i++){
33             ArrayList listTem = new ArrayList();
34             listTem = listAll.get(i);
35             for(Iterator iter = listTem.iterator();iter.hasNext();){
36                 int lastValue = http://www.mamicode.com/count*count+1 - (int)iter.next();
37 //没有标准化格式的输出
38 //                System.out.print(lastValue+" ");
39                 System.out.printf("%3d ",lastValue);
40             }
41             System.out.println();
42         }
43     }

这里把N=偶数和N=奇数时分开构建开头的情况。其实就矩阵来看,N为偶数与N为奇数之间也可以通过矩阵转置来实现。但开头分开也比较简单实现,所以就用这种途径了。完整代码实现见github:https://github.com/Pengyiqing/java_practice

 

java下蛇形回环矩阵的实现