【华为OD机考真题】- 螺旋数字矩阵(B卷-100分)（C++版）

🔔本文收录于「最新最全华为OD机试真题(C++版)」专栏，手把手带你零基础教学华为OD机试。本题集提供最优题解思路，解题步骤，代码解析，复杂度分析及最优题解源码等，支持多语言题解，助你轻松拿捏OD机考，一举上岸！安利大家关注&&收藏&&订阅！题库正在疯狂收录中，up！up！up！！
🚫提醒：拒绝一切代考/替考，违法必究！专栏所写题库均搜集于互联网，经过精心筛选和整理，结合数位十多年大厂实战经验资深大佬经验所撰，欢迎订阅。
  
💗订阅福利：一次订阅，可永久免费阅读，提供在线答疑解惑，后续题库更新皆可阅读使用！

🔥所有题目均有六种语言实现，汇总如下🔥

• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【全栈版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【Java版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【Python版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【C版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【C++版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【Golang版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【JavaScript版】

如上题库均已同步更新至最新华为OD机试真题，赶紧操练起来吧~~

📚1. 题目描述

📢 具体题目描述如下：

疫情期间，小明隔离在家，百无聊赖，在纸上写数字玩。他发明了一种写法：
给出数字个数n和行数 m (0 < n ≤ 999，0 < m ≤ 999)，从左上角的1开始，按照顺时针螺旋向内写方式，依次写出 2,3…n，最终形成个m 行矩阵。
小明对这个知阵有些要求：

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

温馨提醒： 大家在参加华为OD机试时，切记不要仅仅死记硬背题解代码。真正的通过率取决于你对代码的理解能力。建议你在理解基本原理和逻辑的基础上，模仿并自己编写代码，这样才能更有效地应对机试。

📝2. 输入描述

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

🖥️3. 输出描述

符合要求的唯一短阵

🔍4. 示例演示

✨4.1 示例1

输入：

9 4

输出：

1 2 3* * 49 * 58 7 6

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

✨4.2 示例2

输入：

3 5

输出：

123**

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

✨4.3 示例3

输入：

120 7

输出：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1846 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 1945 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 63 2044 83 114 115 116 117 118 119 120 * * * * * * 99 64 2143 82 113 112 111 110 109 108 107 106 105 104 103 102 101 100 65 2242 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 2341 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24

示例说明：

温馨提醒： 大家在参加华为OD机试时，切记不要仅仅死记硬背题解代码。真正的通过率取决于你对代码的理解能力。建议你在理解基本原理和逻辑的基础上，模仿并自己编写代码，这样才能更有效地应对机试。

🔑5. 解题分析

🤔5.1 问题理解

题目要求我们生成一个 m 行矩阵，其中填充从 1 到 n 的数字，且数字的排列方式是顺时针螺旋填充，剩余的空位用 * 填充。以下是问题的主要要求：

1. 每行数字的个数应该相同。
2. 列的数量尽可能少。
3. 填充数字时，优先从外部开始填充，按顺时针螺旋的方式填充矩阵。
4. 如果数字不足以填满矩阵，剩余的位置用 * 占位。

💡5.2 解题思路

1. 确定列数：

   • 题目要求每行的数字个数相同，因此我们需要计算每行列的数量。列数可以通过公式 k = (n + m - 1) / m 来计算，这样能够确保在 m 行中最少的列数能够容纳所有的数字。

2. 初始化矩阵：

   • 创建一个大小为 m 行 k 列的矩阵，初始状态所有元素为 *。

3. 顺时针螺旋填充矩阵：

   • 从矩阵的外层开始，按照顺时针方向依次填充数字。顺序为：右、下、左、上，依此类推。
   • 填充时，如果数字已经用完，则用 * 填充空余位置。

4. 输出矩阵：

   • 遍历矩阵，输出每一行的内容。

🎯5.3 问题考点

1. 螺旋填充算法：需要理解如何按顺时针方向填充矩阵，确保从外到内逐步填充。
2. 矩阵边界处理：在填充矩阵时，要考虑矩阵的边界，避免越界。
3. 列数计算：根据 n 和 m 来确定最小的列数，保证每行数字个数一致。
4. 填充空位：在数字不足的情况下，用 * 填充空余位置。

📝5.4 解题步骤

1. 输入数据：

   • 读取 n 和 m，分别表示数字的个数和矩阵的行数。

2. 计算列数：

   • 使用 (n + m - 1) / m 来计算列数 k。

3. 初始化矩阵：

   • 创建一个大小为 m 行 k 列的矩阵，初始状态为 *。

4. 螺旋填充矩阵：

   • 设定四个方向：右、下、左、上，依次填充矩阵。填充的数字为 1 到 n，数字不足时填充 *。

5. 输出结果：

   • 输出填充后的矩阵，每行的元素之间用空格隔开。

💻6. 解题Coding

  根据如上题解思路，进行代码实战，大家请看如下，建议不要死记硬背代码，要理解其题型及实现思路，别担心，代码我都会给出超详细注释，你一定能看明白的。

✅6.1 代码实现(C++版)

#include #include #include using namespace std;int main() { int n, m; cin >> n >> m; // 输入数字总数和行数 // 计算每行的列数 int k = (n + m - 1) / m; // 创建一个 m 行 k 列的矩阵并初始化为 \"*\" vector<vector<string>> matrix(m, vector<string>(k, \"*\")); int num = 1; // 当前填充的数字 int x = 0, y = 0; // 当前填充的位置 // 填充矩阵 while (num <= n) { // 向右填充 while (y < k && matrix[x][y] == \"*\") { matrix[x][y] = (num <= n) ? to_string(num) : \"*\"; num++; y++; } // 向下填充 x++; y--; // 向左填充 while (x < m && matrix[x][y] == \"*\") { matrix[x][y] = (num <= n) ? to_string(num) : \"*\"; num++; x++; } x--; y--; // 向上填充 if (x >= 0) { while (y >= 0 && matrix[x][y] == \"*\") { matrix[x][y] = (num <= n) ? to_string(num) : \"*\"; num++; y--; } y++; x--; } // 向右填充 if (y < k) { while (x >= 0 && matrix[x][y] == \"*\") { matrix[x][y] = (num <= n) ? to_string(num) : \"*\"; num++; x--; } x++; y++; } } // 输出矩阵 for (const auto& row : matrix) { for (const auto& element : row) { cout << element << \" \"; } cout << endl; } return 0;}

⏱6.2 时间&空间复杂度

时间复杂度：

• 填充矩阵的过程：每个位置最多填充一次数字。由于矩阵大小为 m 行 k 列，且填充最多 n 个数字，因此填充过程的时间复杂度为 O(m * k)。
• 总体时间复杂度：O(m * k)，其中 m 是行数，k 是列数。

空间复杂度：

• 存储矩阵需要的空间：矩阵的大小为 m * k，因此空间复杂度为 O(m * k)。

⛓‍💥6.3 代码解析

1. 输入部分：

   • 通过 cin 获取数字总数 n 和行数 m。
   • 根据输入的 n 和 m 计算每行需要的列数 k。

2. 矩阵初始化：

   • 使用一个二维 vector 存储矩阵，矩阵大小为 m 行 k 列。初始化所有位置为 *。

3. 螺旋填充：

   • 使用一个 while 循环来填充矩阵，循环条件是数字 num 小于等于 n。
   • 按照螺旋顺序依次填充矩阵：首先从左到右填充，接着向下填充，然后从右到左填充，最后向上填充。
   • 每填充一个位置后，num 增加1，直到填充完所有数字。

4. 输出矩阵：

   • 使用两个嵌套的循环输出矩阵，每行输出矩阵中的元素，元素之间用空格分隔。

核心思想：

• 本问题的关键是根据给定的 n 和 m，按照螺旋顺序填充一个矩阵。在每次填充过程中，通过判断当前矩阵位置是否已经被填充，控制填充的方向。

📝6.4 小结

该程序通过模拟螺旋顺序填充数字矩阵，填充的顺序依次为：从左到右、从下到上、从右到左、从上到下。利用二维 vector 来存储矩阵数据，通过循环模拟螺旋的移动方向。该程序的时间和空间复杂度为 O(m * k)，其中 m 和 k 是矩阵的行和列数。

📥7. 附录源码（Java版）

  针对如上分享OD机试真题之外，这里我还开源全部OD机试原真题源码，供同学们一对一学习！对照每题都有题目号及详细代码注释。Gitee，例如题序号为1，则题解代码对应文件夹OD1，题序号为5，则题解代码对应文件夹OD5，以此类推，目的就是为了方便大家学习，一举上岸！(这里的题序号指专栏导航贴中表格一列的序号)

🧧福利赠与你🧧

  如果你还想学习更多相关OD真题题解，都建议直接毫不犹豫地学习此专栏「最新最全真题华为OD机试真题(全栈版)」，快速掌握Java、Python、C++、JavaScript、Go等多种热门语言详细解题，快速突破华为OD机试，实现350+高分目标。还将提供线上多端答疑交流，解决你的所有问题！

🎁安利其他语言版本题解册🎁

• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【全栈版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【Java版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【Python版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【C版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【C++版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【Golang版】
• 【华为OD机试】最新最全真题汇总A+B+C+D+E卷【JavaScript版】

注意： 上述任意专栏一次订阅，获永久免费阅读权限，后续更新都能学习。
声明： 拒绝一切形式的代考，替考行为，务必诚信考试！！！本人所写题库均搜集于互联网。

👩‍💻Who am I?

我是bug菌，CSDN | 掘金 | InfoQ | 51CTO | 华为云 | 阿里云 | 腾讯云 等社区博客专家，C站博客之星Top30，华为云多年度十佳博主&最具价值贡献奖，掘金多年度人气作者Top40，掘金等各大社区平台签约作者，51CTO年度博主Top12，掘金/InfoQ/51CTO等社区优质创作者；全网粉丝合计 30w+；更多精彩福利点击这里；硬核微信公众号「猿圈奇妙屋」，欢迎你的加入！免费白嫖最新BAT互联网公司面试真题、4000G PDF电子书籍、简历模板等海量资料，你想要的我都有，关键是你不来拿。

-End-