回形遍历二维数组-递归法

2019-03-16

|已阅： 1

回形遍历二维数组一般都会使用循环加数组下标操作实现,实现难度不大但不好理解
我觉得使用递归法实现更好理解一些,首先拆解问题.

回形遍历问题

所谓的回形遍历指的是按顺时指访问二维数组中的每个元素，如下图所示：

1	2	3	4
12	13	14	5
11	16	15	6
10	9	8	7

图1-1

上图为一个4X4的二维数组，按照数字顺序读取这个二维数组就叫做回形遍历

其实换个方法如果能将一个二维数组按图中顺序填充上数据也是一样的道理

递归的思路

递归的参数

看一下图1-1，这种遍历其实就是一圈一圈的写数据，每一圈的不同点只有起始下标及二维数组的宽/高度以及写入的数字起始值，每向里一圈，数组宽度就减2

提取出来的方法参数为:

要返回的二维数组
写入数字的起始值
当前二维数组宽度

递归执行过程

向右写入数据直到行尾
再向下写入到列底
然后向左写到行首
最后向上写入补齐完成的一圈

何时停止递归

图1-1 中最里面是一个宽度为2的数组，也就是说偶数个宽度的数组，当数组循环到入参的二维数组为2是则返回结果再来看一下单数宽度的数组

5X5的二维数组图：

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

图2-1

二维数组最里面是“25”，是一个宽度为1的数组

所以递归的结束条件就是当二维数组的长度为1或者2的时候就停止递归并返回数组

代码实现

使用java代码实现如下：

public class A {
    public static void main(String args[]){
        print(10);
    }

    public static void print(int n){
        int[][] is = new int[n][n];
        is = base(is, 1, n);
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                System.out.print(is[j][i]+ (is[j][i]<10 ? "  ": " "));
            }
            System.out.println();
        }
    }

    /**
     * 写入一整圈操作
     * @param is 要返回的二维数组
     * @param start 起始数字
     * @param n 二维数组宽/高度
     * @return
     */
    public static int[][] base(int[][] is, int start, int n){
        // 取下标起始点
        int i = (is.length-n)/2;
        // 横向初始-1是为了统一做++操作
        int x=i-1,y=i;
        // 向左写入到行尾
        while(x<i+n-1){
            is[++x][y] = start++;
        }
        // 向下写入到底
        while(y<i+n-1){
            is[x][++y] = start++;
        }
        // 向右写入到横向起始点
        while(x>i){
            is[--x][y] = start++;
        }
        // 向上写入完成整圈操作
        while(y>i+1){
            is[x][--y] = start++;
        }
        // 1和2两种情况对应的都不能再继续递归
        if(n==1 || n== 2){
            return is;
        } else {
            return base(is, start, n-2);
        }
    }
}

代码基本都有注释很好理解，其实就是把前面说的思路实现了一下，输出的内容如下：

#4X4
1  2  3  4  
12 13 14 5  
11 16 15 6  
10 9  8  7  

#5X5
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

本文作者： ixx
本文链接： http://blog.jisuye.com/2019/03/16/shape_traversal/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！