黑马程序员技术交流社区

标题: 螺旋数组简单实现,求优化. [打印本页]

---

作者: 陈圳    时间: 2013-5-3 19:40
标题: 螺旋数组简单实现,求优化.


以前解过螺旋数组,但是开始是用一种很烦琐的方式完成.以致于代码到后自己都看不下去.让我重做我也有当时那个思路,但是完成写出来,却是异常麻烦.
昨天正好解了另一道题.获得思路,于是以一种其他的方式,可以更简单的实现了螺旋数组.
下面给出分析过程:

代码如下:

1. public class LineArray {
   
2. 
   
3.         /**螺旋数组的
   
4.          * @param args
   
5.          */
   
6.         public static void main(String[] args) {
   
7.                 createArray(7);
   
8.         }
   
9.         public static void createArray(int n){
   
10.                 int index=1;
    
11.                 Direction dir=Direction.D;
    
12.                 int[][] arr=new int[n][n];
    
13.                 int row=n/2,col=n/2,temp=0,step=0;
    
14.                 while(index!=n*n){
    
15. //                        temp=(step%2==0)?temp+1:temp;
    
16.                         if(step%2==0&&step!=(n-1)*2)//这里控制步数的变化,也就是让方向执行到D或A时,步数才增加,其余不加
    
17.                                 temp++;
    
18.                         if(dir==Direction.D){
    
19.                                 for(int i=0;i<temp;i++){
    
20.                                         arr[row][++col]=++index;
    
21.                                 }
    
22.                                 step++;
    
23.                         } else if(dir==Direction.S){
    
24.                                 for(int i=0;i<temp;i++){
    
25.                                         arr[++row][col]=++index;
    
26.                                 }
    
27.                                 step++;
    
28.                         } else if(dir==Direction.A){
    
29.                                 for(int i=0;i<temp;i++){
    
30.                                         arr[row][--col]=++index;
    
31.                                 }
    
32.                                 step++;
    
33.                         } else if(dir==Direction.W){
    
34.                                 for(int i=0;i<temp;i++){
    
35.                                         arr[--row][col]=++index;
    
36.                                 }
    
37.                                 step++;
    
38. }
    
39.                         dir=dir.nextDirection();//每执行一步,方向会发生变化.变化过程 D->S->A->W
    
40.                         for(int i=0;i<arr.length;i++)//打印每一步数组的变化
    
41.                                 System.out.println(Arrays.toString(arr[i]));
    
42.                         System.out.println("----------------------------------------");
    
43.                 }
    
44.         }
    
45. 
    
46. }
    
47. enum Direction{
    
48.         D,S,A,W;//四个方向,螺旋数组的行走方向
    
49.         public Direction nextDirection(){//循环四个方向
    
50.                 switch(this){
    
51.                         case D:return S;
    
52.                         case S:return A;
    
53.                         case A:return W;
    
54.                         case W:return D;
    
55.                 }
    
56.                 return null;
    
57.         }
    
58. }

复制代码

中间会有一个没有赋值,赋不赋值无所谓了.最主要的是代码有很大的优化余地.因为思路容易懂.
如果哪个高人有空研究,希望能优化一些.谢谢.

---

作者: lipingan0520    时间: 2013-5-3 20:06
能打印出每一步的变化过程，你没考虑偶数的情况吗？:)

---

作者: 陈圳    时间: 2013-5-3 20:22

lipingan0520 发表于 2013-5-3 20:06
能打印出每一步的变化过程，你没考虑偶数的情况吗？

这个实现了,偶数的就很好实现,有两种方式.第一种,直接取这个方法,返回一个奇数的,再赋上外围的一圈,就能给出一个偶数的排列,
那次挑战时,用的就是那个思路解决的.
当时的思路代码阅读性差.

1. public static int[][] getArray2(int num,int index){//这个是偶数
   
2.              int[][] arr=new int[num][num];
   
3.              int[][] temp=getArray1(num-1,index);//这里调用第一个奇数方法,得到奇数螺旋的数组.然后在外围加上一圈就行了
   
4.              for(int i=0;i<temp.length;i++)//这里赋值,但总感觉有更好的方式完成这步...
   
5.                      for(int j=0;j<temp[i].length;j++){
   
6.                              arr[i][j]=temp[i][j];
   
7.                      }
   
8.              int count=num*num,length=num*2-1;//这里等于4--16;
   
9.              for(int i=0;i<=length;i++){//赋上最外层一圈
   
10.                      if(i<num)
    
11.                              arr[num-1][i]=count--;
    
12.                      else
    
13.                              arr[length-i][num-1]=count--;
    
14.              }
    
15.          return arr;
    
16.     }

复制代码

第二种就是直接改变起始的位置,都很容易实现,发帖交流最主要是获得一些更好的思路.后期的一些简单实现,我感觉实现不实现就无所谓了.

---

作者: 陈圳    时间: 2013-5-3 20:36

1. public class LineArray {
   
2. 
   
3.         /**
   
4.          * 螺旋数组的
   
5.          *
   
6.          * @param args
   
7.          */
   
8.         public static void main(String[] args) {
   
9.                 createArray(7,true);//true为顺时针输出,false为逆时针输入
   
10.         }
    
11. 
    
12.         public static void createArray(int n,boolean flag) {//加入一个标记,可以实现逆时针或者顺时针螺旋输出
    
13.                 int index = 1;
    
14.                 Direction dir;
    
15.                 if(flag)
    
16.                          dir= Direction.D;
    
17.                 else dir= Direction.A;
    
18.                 int[][] arr = new int[n][n];
    
19.                 int row = n / 2, col = n / 2, temp = 0, step = 0;
    
20.                 while (index != n * n) {
    
21.                         // temp=(step%2==0)?temp+1:temp;
    
22.                         if (step % 2 == 0 && step != (n - 1) * 2)
    
23.                                 temp++;
    
24.                         if (dir == Direction.D) {
    
25.                                 for (int i = 0; i < temp; i++) {
    
26.                                         arr[row][++col] = ++index;
    
27.                                 }
    
28.                                 step++;
    
29.                         } else if (dir == Direction.S) {
    
30.                                 for (int i = 0; i < temp; i++) {
    
31.                                         arr[++row][col] = ++index;
    
32.                                 }
    
33.                                 step++;
    
34.                         } else if (dir == Direction.A) {
    
35.                                 for (int i = 0; i < temp; i++) {
    
36.                                         arr[row][--col] = ++index;
    
37.                                 }
    
38.                                 step++;
    
39.                         } else if (dir == Direction.W) {
    
40.                                 for (int i = 0; i < temp; i++) {
    
41.                                         arr[--row][col] = ++index;
    
42.                                 }
    
43.                                 step++;
    
44.                         }
    
45.                         dir = dir.nextDirection(flag);
    
46.                         for (int i = 0; i < arr.length; i++)
    
47.                                 System.out.println(Arrays.toString(arr[i]));
    
48.                         System.out.println("----------------------------------------");
    
49.                 }
    
50.         }
    
51. 
    
52. }
    
53. 
    
54. enum Direction {
    
55.         D, S, A, W;// 四个方向,螺旋数组的行走方向
    
56.         public Direction nextDirection(boolean flag) {// 循环四个方向
    
57.                 if(flag){
    
58.                         switch (this) {
    
59.                         case D:        return S;
    
60.                         case S:        return A;
    
61.                         case A:        return W;
    
62.                         case W:        return D;
    
63.                         }
    
64.                 } else {
    
65.                         switch (this) {
    
66.                         case A:        return S;
    
67.                         case S:        return D;
    
68.                         case D:        return W;
    
69.                         case W:        return A;
    
70.                         }
    
71.                 }
    
72.                 return null;
    
73.         }
    
74.        
    
75. }

复制代码

因为枚举方向的变化控制,所以简单实现了,程序的逆时针与逆时针的分别输出.

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

复制代码

---

作者: 陈圳    时间: 2013-5-3 21:22
最后优后了...

1. import java.util.Arrays;
   
2. public class LineArray {
   
3.         public static void main(String[] args) {
   
4.                 createArray(4,true);//true为顺时针输出,false为逆时针输入
   
5.         }
   
6.         public static void createArray(int n,boolean flag) {//加入一个标记,可以实现逆时针或者顺时针螺旋输出
   
7.                 Direction dir;
   
8.                 if(flag)//判断顺时针逆时针方向
   
9.                          dir= Direction.D;
   
10.                 else dir= Direction.A;
    
11.                 int[][] arr = new int[n][n];
    
12.                 int row,col,temp = 0,step = 0,index = 1;;
    
13.                 if(n%2==0)//判断是奇数二维数组还是偶数
    
14.                         row=col=n/2-1;
    
15.                 else row=col=n/2;
    
16.                 arr[row][col]=1;
    
17.                 while (index != n * n) {
    
18.                         if (step % 2 == 0 && step != (n - 1) * 2)
    
19.                                 temp++;
    
20.                         for(int i=0;i<temp;i++){//每个方向的循环次数
    
21.                                 switch(dir){
    
22.                                         case D:arr[row][++col]=++index;break;
    
23.                                         case S:arr[++row][col]=++index;break;
    
24.                                         case A:arr[row][--col]=++index;break;
    
25.                                         case W:arr[--row][col]=++index;break;
    
26.                                 }
    
27.                                 if(i==temp-1)
    
28.                                         step++;
    
29.                         }
    
30.                         dir = dir.nextDirection(flag);
    
31.                         for (int i = 0; i < arr.length; i++)
    
32.                                 System.out.println(Arrays.toString(arr[i]));
    
33.                         System.out.println("----------------------------------------");
    
34.                 }
    
35.         }
    
36. }
    
37. enum Direction {
    
38.         D, S, A, W;// 四个方向,螺旋数组的行走方向
    
39.         public Direction nextDirection(boolean flag) {// 循环四个方向
    
40.                 if(flag){
    
41.                         switch (this) {
    
42.                         case D:        return S;
    
43.                         case S:        return A;
    
44.                         case A:        return W;
    
45.                         case W:        return D;
    
46.                         }
    
47.                 } else {
    
48.                         switch (this) {
    
49.                         case A:        return S;
    
50.                         case S:        return D;
    
51.                         case D:        return W;
    
52.                         case W:        return A;
    
53.                         }
    
54.                 }
    
55.                 return null;
    
56.         }
    
57. }
    

复制代码

---

作者: 刘胜寒    时间: 2013-5-3 21:46
赤裸裸的 显摆啊...回帖有奖励吗？？{:soso_e102:}

---

作者: 陈圳    时间: 2013-5-3 21:53

刘胜寒 发表于 2013-5-3 21:46
赤裸裸的 显摆啊...回帖有奖励吗？？

只有沙发有...以前一次散的多了.结果发现没人回帖,金币会系统收了...蛋疼
现在每次发帖沙发先来50,多霸气!

---

作者: 李德全    时间: 2013-5-3 22:00
楼主，我就是用的着方法哦，{:soso_e109:}

---

作者: 陈圳    时间: 2013-5-3 22:30

李德全 发表于 2013-5-3 22:00
楼主，我就是用的着方法哦，

用这种方法很正常.思路想到一块了,代块肯定就跑不远.你把代码也发过来,我们交流一下.这个思路优化空间很大.

---

作者: 王瑞    时间: 2013-5-4 08:03
高手啊，顶一下~

---

作者: 李德全    时间: 2013-5-4 08:58

陈圳 发表于 2013-5-3 22:30
用这种方法很正常.思路想到一块了,代块肯定就跑不远.你把代码也发过来,我们交流一下.这个思路优化空间很 ...

在那个帖子上

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2