当前位置：首页 > news >正文

华为OD机试 - 螺旋数字矩阵 - 矩阵（Python/JS/C/C++ 2024 D卷 100分）

news 2024/10/27 15:47:01

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

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

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

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

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

二、输入描述

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

三、输出描述

符合要求的唯一矩阵

四、测试用例

1、输入

9 4

2、输出

在这里插入图片描述

3、说明

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

五、解题思路

计算列数：根据给定的数字个数n和行数m，计算最少需要的列数cols，使得每行数字个数相同，并且列数尽可能少。计算公式为cols = ceil(n / m)。
初始化矩阵：创建一个m x cols的矩阵，初始化所有位置为*，表示占位符。
螺旋填充数字：
- 使用四个指针top, bottom, left, right来定义当前的填充边界。
- 按照顺时针的顺序依次向右、向下、向左、向上填充数字。
- 每填充一个数字，数字计数器num递增。
- 当num超过n时，停止填充，剩余位置保持*。
输出矩阵：按照行顺序输出填充后的矩阵，每行数字之间用空格分隔。

六、Python算法源码

import mathdef spiral_matrix(n, m):# 计算需要的最少列数cols = math.ceil(n / m)# 初始化矩阵，填充'*'matrix = [['*' for _ in range(cols)] for _ in range(m)]# 螺旋填充数字num = 1top, bottom = 0, m - 1left, right = 0, cols - 1while num <= n:# 向右移动for i in range(left, right + 1):if num > n:breakmatrix[top][i] = str(num)num += 1top += 1# 向下移动for i in range(top, bottom + 1):if num > n:breakmatrix[i][right] = str(num)num += 1right -= 1# 向左移动for i in range(right, left - 1, -1):if num > n:breakmatrix[bottom][i] = str(num)num += 1bottom -= 1# 向上移动for i in range(bottom, top - 1, -1):if num > n:breakmatrix[i][left] = str(num)num += 1left += 1# 输出矩阵for row in matrix:print(' '.join(row))# 读取输入
n, m = map(int, input().split())
spiral_matrix(n, m)

七、JavaScript算法源码

function spiralMatrix(n, m) {// 计算需要的最少列数const cols = Math.ceil(n / m);// 初始化矩阵，填充'*'const matrix = Array.from({ length: m }, () => Array(cols).fill('*'));// 螺旋填充数字let num = 1;let top = 0, bottom = m - 1;let left = 0, right = cols - 1;while (num <= n) {// 向右移动for (let i = left; i <= right && num <= n; i++) {matrix[top][i] = String(num++);}top++;// 向下移动for (let i = top; i <= bottom && num <= n; i++) {matrix[i][right] = String(num++);}right--;// 向左移动for (let i = right; i >= left && num <= n; i--) {matrix[bottom][i] = String(num++);}bottom--;// 向上移动for (let i = bottom; i >= top && num <= n; i--) {matrix[i][left] = String(num++);}left++;}// 输出矩阵for (let row of matrix) {console.log(row.join(' '));}
}// 读取输入
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf-8').trim().split(' ');
const n = parseInt(input[0]);
const m = parseInt(input[1]);
spiralMatrix(n, m);

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>int main() {int n, m;// 读取输入的n和mscanf("%d %d", &n, &m);// 计算需要的最少列数int cols = (int)ceil((double)n / m);// 动态分配二维数组，并初始化为'*'char ***matrix = (char ***)malloc(m * sizeof(char **));for(int i = 0; i < m; i++) {matrix[i] = (char **)malloc(cols * sizeof(char *));for(int j = 0; j < cols; j++) {matrix[i][j] = (char *)malloc(2 * sizeof(char));strcpy(matrix[i][j], "*");}}// 螺旋填充数字int num = 1;int top = 0, bottom = m -1;int left = 0, right = cols -1;while(num <= n) {// 向右移动for(int i = left; i <= right && num <= n; i++) {char buffer[12];sprintf(buffer, "%d", num++);strcpy(matrix[top][i], buffer);}top++;// 向下移动for(int i = top; i <= bottom && num <= n; i++) {char buffer[12];sprintf(buffer, "%d", num++);strcpy(matrix[i][right], buffer);}right--;// 向左移动for(int i = right; i >= left && num <= n; i--) {char buffer[12];sprintf(buffer, "%d", num++);strcpy(matrix[bottom][i], buffer);}bottom--;// 向上移动for(int i = bottom; i >= top && num <= n; i--) {char buffer[12];sprintf(buffer, "%d", num++);strcpy(matrix[i][left], buffer);}left++;}// 输出矩阵for(int i = 0; i < m; i++) {for(int j = 0; j < cols; j++) {if(j > 0) printf(" ");printf("%s", matrix[i][j]);}printf("\n");}// 释放内存for(int i = 0; i < m; i++) {for(int j = 0; j < cols; j++) {free(matrix[i][j]);}free(matrix[i]);}free(matrix);return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;int main(){int n, m;// 读取输入的n和mcin >> n >> m;// 计算需要的最少列数int cols = ceil((double)n / m);// 初始化矩阵，填充'*'vector<vector<string>> matrix(m, vector<string>(cols, "*"));// 螺旋填充数字int num = 1;int top = 0, bottom = m -1;int left = 0, right = cols -1;while(num <= n){// 向右移动for(int i = left; i <= right && num <=n; i++){matrix[top][i] = to_string(num++);}top++;// 向下移动for(int i = top; i <= bottom && num <=n; i++){matrix[i][right] = to_string(num++);}right--;// 向左移动for(int i = right; i >= left && num <=n; i--){matrix[bottom][i] = to_string(num++);}bottom--;// 向上移动for(int i = bottom; i >= top && num <=n; i--){matrix[i][left] = to_string(num++);}left++;}// 输出矩阵for(int i =0; i < m; i++){for(int j=0; j < cols; j++){if(j >0) cout << " ";cout << matrix[i][j];}cout << "\n";}return 0;
}