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

2024-01-09 14:38:08

OD统一考试(C卷)

分值: 100分

题解: Java / Python / C++

alt

题目描述

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

给出数字个数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 5454. 螺旋矩阵中等
LeetCode LCR 146LCR 146. 螺旋遍历二维数组中等

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

文章来源:https://blog.csdn.net/user_longling/article/details/135478434
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。