螺旋数字矩阵 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

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

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

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

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

输入描述

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

输出描述

符合要求的唯一矩阵

示例1

输入：
9 4

输出：
1 2 3
* * 4
9 * 5
8 7 6

说明：
9个数字写成4行，最少需要3列

示例2

输入：
3 5

输出：
1
2
3
*
*

说明：
3个数字写5行，只有一列，数字不够用*号填充

题解

这是一个模拟题，主要考察对矩阵的遍历和填充的能力。

1. 首先，通过输入获取数字个数n和行数m。
2. 计算矩阵的列数cols，根据题意，最少需要的列数是(n-1) / m + 1。
3. 初始化一个大小为m行cols列的矩阵，所有元素初始值为"*"。
4. 使用四个变量top、bottom、left、right来表示当前矩阵的上下左右边界。
5. 使用cur变量表示当前要填充的数字，从1开始。
6. 进入循环，按照顺时针螺旋的方式依次填充矩阵的数字。
   • 从左到右：遍历当前行的左右范围，依次填充数字。
   • 从上到下：遍历当前列的上下范围，依次填充数字。
   • 从右到左：遍历当前行的右左范围，依次填充数字。
   • 从下到上：遍历当前列的下上范围，依次填充数字。
7. 在每次填充后，更新相应的边界。
8. 循环直到所有数字都填充完毕。
9. 最后，输出填充好的矩阵。

这样，通过模拟顺时针螺旋填充的过程，就能得到符合要求的矩阵。

Java

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int rows = m, cols = (n - 1) / m + 1;

        // grid[i][j] == 0 则认为数字不够为 *
        int[][] grid = new int[rows][cols];

        // 上下左右，四侧的边界
        int top = 0, bottom = rows - 1, left = 0, right = cols - 1;
        int cur = 1;
        while (cur <= n) {
            // 从左到右
            for (int i = left; i <= right && cur <= n; i++) {
                grid[top][i] = cur++;
            }
            if (++top > bottom) break; // 收缩范围

            // 从上到下
            for (int i = top; i <= bottom && cur <= n; i++) {
                grid[i][right] = cur++;
            }
            if (--right < left) break; // 收缩范围

            // 从右到左
            for (int i = right; i >= left && cur <= n; i--) {
                grid[bottom][i] = cur++;
            }
            if (--bottom < top) break; // 收缩范围

            // 从下到上
            for (int i = bottom; i >= top && cur <= n; i--) {