算法（18）给女朋友讲明白校招时的面试题，【回形矩阵、回形取数】

写在前面： 我是 扬帆向海，这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。技术是开源的、知识是共享的。

这博客是对自己学习的一点点总结及记录，如果您对 Java、算法 感兴趣，可以关注我的动态，我们一起学习。

用知识改变命运，让我们的家人过上更好的生活。

把写过的算法文章全放在这儿了，点链接可以直达！

算法系列文章

---

---

我：面试怎么样？（原谅咱们都是理工科直男）

她： 。。。

我： 面试有没有做笔试题?

她：做了

我：什么题？

她：一道算法题

我：你大概说说题目

她：是一道回形取数的算法题

我： 哦。。。这题不至于哭吧！

一、题目分析

输入一个整数，则以该数字为矩阵的大小，把1,2,3…n*n 的数字按照顺时针螺旋的形式填入其中。

例如：

输入数字2，则程序输出：
1 2
4 3

输入数字3，则程序输出：
1 2 3
8 9 4
7 6 5

二、算法分析

回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则旋转90度。一开始位于矩阵左上角，方向向右。按顺时针方向旋转进行取值。

类似于贪吃蛇，碰到 障碍 或 边界 就要改变方向

先不急，我来给你画一张图，慢慢分析：

把每一个数字当作矩阵中的一个点，输出顺序是从外圈到内圈的顺时针顺序。以最外圈为例，其输出为从（0,0）到（2,0）为红色点，其次输出是黄色点，再次输出是蓝色点，最后输出是绿色点，按照顺时针的顺序，到此外圈输出完毕。

从（0,0）点开始，开始向右取值，可以画出这样的图形

从上面的图形我们发现如下规律：

x 表示列， y 表示行

通过以上的规律，每次输出都需要更换不同的起始点，可以通过4个 for 循环依次输出红色、黄色、蓝色、绿色四个点，直至全部输完。

关于输出矩阵，大多数人都会认为使用数组最为方便，所以这里使用二维数组来实现。

使用一个二维数组 array 来存放数据，最后遍历输出这些数据

第一圈输出完毕后，又会按上述规律循环输出第二圈。。。

我：明白了没？

她：明白了

我：那你写一下代码，实现上面说说的逻辑

她噼里啪啦一顿操作就写完了（此处代码有bug，望耐心看完后面的）

---

public class RectangleTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入矩阵阶数：");
        int n = scanner.nextInt();
        printRectangle(n);
    }

	 /**
     * 回形矩阵
     *
     * @param n
     */
    private static void printRectangle(int n) {
        // 创建一个二维数组
        int[][] array = new int[n][n];
        // num 表示第几个数字
        int num = 1;

        // 外层循环 i 控制圈数,内层循环 j 控制第几条线
        for (int i = 0; i < n / 2; i++) {
            // 第一条线 上线
            // x 表示列， y 表示行
            for (int y = i, x = i; x < n - i - 1; x++) {
                array[y][x] = num++;
            }
            // 第二条线 右线
            for (int y = i, x = n - i - 1; y < n - i - 1; y++) {
                array[y][x] = num++;
            }
            // 第三条线 下线
            for (int y = n - i - 1, x = n - i - 1; x > i; x--) {
                array[y][x] = num++;
            }
            // 第四条线 左线
            for (int y = n - i - 1, x = i; y > i; y--) {
                array[y][x] = num++;
            }
        }
        
        // 遍历打印输出数字
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                System.out.print(array[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

这是她写的代码，我让测试一下

她感觉很开心，我说你再输入一个3或5，再测试一下

我：发现没，当输入的数字是奇数的时候，中间数字有问题。

我：是不是可以做个判断，对输入的数字进行区分，当N阶矩阵是一个偶数阶的矩阵时没有矩阵中心元素，但是奇数阶矩阵有矩阵中心元素

她：直接输出最后那个数字。。。

if (n % 2 == 1) {
	array[n / 2][n / 2] = num;
}

三、完整的代码实现

public class RectangleTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入矩阵阶数：");
        int n = scanner.nextInt();
        printRectangle(n);
    }

	 /**
     * 回形矩阵
     *
     * @param n
     */
    private static void printRectangle(int n) {
        // 创建一个二维数组
        int[][] array = new int[n][n];
        // num 表示要显示的数字
        int num = 1;

        // 外层循环 i 控制圈数,内层循环 j 控制第几条线
        for (int i = 0; i < n / 2; i++) {
            // 第一条线 上线
            // x 表示列， y 表示行
            for (int y = i, x = i; x < n - i - 1; x++) {
                array[y][x] = num++;
            }
            // 第二条线 右线
            for (int y = i, x = n - i - 1; y < n - i - 1; y++) {
                array[y][x] = num++;
            }
            // 第三条线 下线
            for (int y = n - i - 1, x = n - i - 1; x > i; x--) {
                array[y][x] = num++;
            }
            // 第四条线 左线
            for (int y = n - i - 1, x = i; y > i; y--) {
                array[y][x] = num++;
            }
        }

        // 对输入的阶数进行判断
        if (n % 2 == 1) {
            array[n / 2][n / 2] = num;
        }

        // 遍历打印输出数字
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                System.out.print(array[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

测试结果：

---

由于水平有限，本博客难免有不足，恳请各位大佬不吝赐教！

转载：https://blog.csdn.net/weixin_43570367/article/details/103993738