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

题目描述与示例

题目描述

疫情期间，小明隔离在家，百无聊赖，在纸上写数字玩。
他发明了一种写法：给出数字个数n和行数m (0 < n < 999，0 < m < 999)，从左上角的1开始，按照顺时针螺旋向内写方式，依次写出2, 3, …, n，最终形成一个m行矩阵。
小明对这个矩阵有些要求：

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

输入描述

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

输出描述

符合要求的唯一短阵

示例

输入

9 4

输出

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

题目思路

和LeetCode 54. 螺旋矩阵类似。
本题只给出了矩阵的行数m，没有给列数，需要我们求解一个最少的列数来满足矩阵能够填入n个数字，因此列数 k = ceil(n / m)，这里的除法不是整除，并且要对除法的结果向上取整。

参考代码

import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
    public static void main(String[] args) {
        // 输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        // 矩阵列数
        int k = (int) Math.ceil(n * 1.0 / m);

        String[][] matrix = new String[m][k];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                matrix[i][j] = "*";
            }
        }
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        boolean[][] visited = new boolean[m][k];
        for (int i = 0; i < n; i++) {
            matrix[row][column] = String.valueOf(i + 1);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0];
            int nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= m || nextColumn < 0 || nextColumn >= k || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }

        // 输出
        for (int i = 0; i < m; i++) {
            StringJoiner rowOutput = new StringJoiner(" ");
            for (int j = 0; j < k; j++) {
                rowOutput.add(matrix[i][j]);
            }
            System.out.println(rowOutput);
        }
    }
}