螺旋数字矩阵 - 华为OD统一考试

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--) {
                grid[i][left] = cur++;
            }
            if (++left > right) break; // 收缩范围
        }

        // 输出结果
        Arrays.stream(grid)
                .map(row -> Arrays.stream(row)
                        .mapToObj(num -> num == 0 ? "*" : String.valueOf(num))
                        .collect(Collectors.joining(" ")))
                .forEach(System.out::println);

    }
}

Python

n, m  = map(int, input().split())

# 计算需要的列数 cols
rows, cols = m, (n - 1) // m + 1

# 初始化矩阵所有值为*
grid = [['*'] * cols for _ in range(rows)]

# 上下左右，四侧的边界
top, bottom, left, right = 0, rows - 1, 0, cols - 1

cur = 1
while True:
    # 从左到右
    for i in range(left, right + 1):
        if cur <= n:
            grid[top][i] = cur
            cur += 1

    top += 1 # 收缩范围
    if top > bottom: break

    # 从上到下
    for i in range(top, bottom + 1):
        if cur <= n:
            grid[i][right] = cur
            cur += 1
    right -= 1 # 收缩范围
    if right  < left: break

    # 从右到左
    for i in range(right, left - 1, -1):
        if cur <= n:
            grid[bottom][i] = cur
            cur += 1
    bottom -= 1 # 收缩范围
    if bottom < top: break

    # 从下到上
    for i in range(bottom, top-1, -1):
        if cur <= n:
            grid[i][left] = cur
            cur += 1
    left += 1 # 收缩范围
    if left > right: break

for row in grid:
    print(" ".join(map(str, row)))


        

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int rows = m, cols = (n - 1) / m + 1;

    // grid[i][j] == 0 则认为数字不够为 *
    vector<vector<int>> grid(rows, vector<int>(cols, 0));

    // 上下左右，四侧的边界
    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--) {
            grid[i][left] = cur++;
        }
        if (++left > right) break; // 收缩范围
    }

    // 输出结果
    for (const auto &row : grid) {
        for (size_t i = 0; i < row.size(); ++i) {
            if (row[i] == 0) {
                cout << "*";
            } else {
                cout << row[i];
            }

            if (i + 1 != row.size()) cout << " ";
            else cout << endl;
        }
    }

    return 0;
}

相关练习题

题号	题目	难易
LeetCode 54	54. 螺旋矩阵	中等
LeetCode LCR 146	LCR 146. 螺旋遍历二维数组	中等

🙏整理题解不易， 如果有帮助到您，请给点个赞 ???? 和收藏 ?，让更多的人看到。🙏🙏🙏