华为OD机试 - 螺旋数字矩阵

1 题目描述

疫情期间，小明隔离在家，百无聊赖，在纸上写数字玩。他发明了一种写法：

给出数字个数 n （0 < n ≤ 999）和行数 m（0 < m ≤ 999），从左上角的 1 开始，按照顺时针螺旋向内写方式，依次写出2,3,…,n，最终形成一个 m 行矩阵。

小明对这个矩阵有些要求：

每行数字的个数一样多
列的数量尽可能少
填充数字时优先填充外部
数字不够时，使用单个 * 号占位

2 输入描述

两个整数，空格隔开，依次表示 n、m

3 输出描述

符合要求的唯一矩阵

4 用例

4.1 用例1

输入

9 4
1

输出

1 2 3
* * 4
9 * 5
8 7 6
1
2
3
4

4.2 用例2

输入

3 5
1

输出

1
2
3
*
*
1
2
3
4
5

5 题目分析·

考点：这道题考的是对二维数组的使用。
解析：题目中比较容易钻牛角尖的描述是每行数字的个数一样多。这句实际上是矩阵的特点，可以忽略。读完题目，我们发现有两个问题需要解决

1. 确定矩阵的列数
2. 设计填充的算法
1
2

通过列的数量尽可能少这个需求，我们可以想到，最少的情况，即矩阵中填充的全都是数字。那么列数= 填充的数字个数n/行数向上取整。
然后是如何填充，这就涉及到了二维数组的螺旋形遍历。我们可以想象一个人在背包容量限制下，在顺时针绕圈捡东西，当不为0，则为已捡过，即换方向捡。

6 Java代码

根据5中的思路，我们可以写出如下代码（代码中给出了详细的注释）：

public class SpiralMatrix {
    public static void main(String[] args) {
        //这里n和m可以修改为使用Scanner从控制台读取输入
        int n = 120;
        int m = 7;
        int columnCount=Math.ceilDiv(n,m);
        int[][] matrix = new int[m][columnCount];
        fillSpiral(matrix,n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < columnCount; j++) {
                System.out.printf("%2s ", matrix[i][j] == 0 ? "*" : matrix[i][j]);
            }
            System.out.println();
        }
    }

    public static void fillSpiral(int[][] matrix, int total) {
        // 将要填充的数字，从1开始
        int num = 1;
        // 方向变量，四个元素分别表示：向右，向下，向左，向上
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 初始化方向变量的索引，0表示初始方向为向右
        int dir = 0;
        // 初始化行列索引
        int row = 0, col = 0;
        // 继续填充，直到所有的数字被填充完
        while (num <= total) {
            // 将数字填充到矩阵的当前位置，然后数字加1
            matrix[row][col] = num++;
            // 尝试按照当前方向去获取新的行列索引
            int newRow = row + directions[dir][0];
            int newCol = col + directions[dir][1];
            // 检查新的行列索引是否超出矩阵的边界，或者该位置已经被填充过
            // 如果是，则将方向变量的索引加1（取模为了形成循环：向右，向下，向左，向上）
            if (newRow < 0 || newRow >= matrix.length || newCol < 0 || newCol >= matrix[0].length || matrix[newRow][newCol] != 0) {
                dir = (dir + 1) % 4;
            }
            // 根据新的方向更新行列索引
            row += directions[dir][0];
            col += directions[dir][1];
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45