华为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 2 3
* * 4
9 * 5
8 7 6

4.2 用例2

输入

3 5

输出

1
2
3
*
*

5 题目分析·

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

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) {// 将数字填充到矩阵的当前位置，然后数字加1matrix[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];}}
}