华为OD机试 - 螺旋数字矩阵 - 矩阵(Python/JS/C/C++ 2024 D卷 100分)
华为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;
}
🏆下一篇:华为OD机试真题 - 简易内存池(Python/JS/C/C++ 2024 E卷 200分)
🏆本文收录于,华为OD机试真题(Python/JS/C/C++)
刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新。