华为OD机试 - 螺旋数字矩阵（Java & JS & Python & C & C++）

题目描述

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

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

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

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

输入描述

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

输出描述

符合要求的唯一矩阵

用例

输入	9 4
输出	1 2 3 * * 4 9 * 5 8 7 6
说明	9个数字写出4行，最少需要3列

输入	3 5
输出	1 2 3 * *
说明	3个数字写5行，只有一列，数字不够用*号填充

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

题目解析

本题需要我们将1~n数字按照螺旋顺序填入矩阵。

本题只给出了矩阵的行数m，没有给列数，需要我们求解一个最少的列数来满足矩阵能够填入n个数字，因此列数 k = ceil(n / m)，这里的除法不是整除，并且要对除法的结果向上取整。

将数字1~n按照螺旋顺序，从矩阵matrix左上角开始填入，比较考察思维能力，具体实现如下：

• 定义变量step，初始step=1，表示当前要填入的数字，因此step ≤ n
• 定义变量x，y，初始x=0, y=0，表示要填值得矩阵位置，即初始时从矩阵左上角开始填入

然后按照顺序循环进行下面四个填值操作：

1. 正序填入第X行
2. 正序填入第Y列
3. 倒序填入第X行
4. 倒序填入第Y列

具体行为如下：

正序填入第x行

初始时，X,Y处于下面位置

按照螺旋顺序，我们应该正序填第X行，即此时行号X不变，列号Y++，具体操作是：

matrix[x][y++] = step++

当列号 Y >= k 时停止填值。如下图所示：此时 X = 0，Y = k

正序填入第y列

按照螺旋顺序，下一步我们应该做一次X++, Y--，让填值位置移动到（X,Y）位置

开始正序填第Y列，即此时列号Y保持不变，行号X++，具体操作是：

matrix[x++][y] = step++

当行号X >= m 时停止填值。如下图所示：此时X=n，Y = k - 1

倒序填入第x行

按照螺旋顺序，下一步我们应该做一次X--, Y--，让填值位置移动到（X,Y）位置

开始倒序填第X行，即此时行号X保持不变，列号Y--，具体操作是：

matrix[x][y--] = step++

当行号Y < 0 时停止填值。如下图所示：此时 X=n-1，Y = -1

倒序填入第y列

按照螺旋顺序，下一步我们应该做一次X--, Y++，让填值位置移动到（X,Y）位置

开始倒序填第Y列，即此时行号X--，列号Y保持不变，具体操作是：

matrix[x--][y] = step++

当行号X < 0 时停止填值。如下图所示：此时 X=-1，Y = 0

但是，此时不符合用例1要求，因为step只需要填到n即可，而用例1的n=9，因此填值过程中，我们需要增加一个判断，即step > n时彻底停止添值，即到下面状态时停止。

假设用例1修改为：

11 4

那么下面状态也是不对的

因为11覆盖掉了该位置添的值1，

因此填值过程如果发现，要添值位置已经有值了，比如下图X--后，发现(X,Y)位置已经填过值了，此时我们应该结束当前方向的添值

按照螺旋顺序，下一个添值位置应该如下图所示：

此时应该基于前一个状态进行X++，Y++，到达上图黄色位置后，此时又回到螺旋顺序的第一步，从第X行开始正序填入。

JS算法源码

1. const rl = require("readline").createInterface({ input: process.stdin });
2. var iter = rl[Symbol.asyncIterator]();
3. const readline = async () => (await iter.next()).value;
5. void (async function () {
6. // n 表示需要在螺旋矩阵中填入 1 ~ n 数字
7. // m 是螺旋矩阵行数
8. const [n, m] = (await readline()).split(" ").map(Number);
10. // k 是螺旋矩阵列数
11. const k = Math.ceil(n / m);
13. // 螺旋矩阵，未填值位置默认值"*"
14. const matrix = new Array(m).fill(0).map(() => new Array(k).fill("*"));
16. // 当前要填入的值
17. let step = 1;
19. // 当前要填入的值的位置
20. let x = 0;
21. let y = 0;
23. // 如果填入的值 > n，则停止填值，否则继续填
24. while (step <= n) {
25. // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
26. while (y < k && matrix[x][y] == "*" && step <= n) matrix[x][y++] = step++;
27. // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步
28. y -= 1;
29. // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列
30. x += 1;
32. // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
33. while (x < m && matrix[x][y] == "*" && step <= n) matrix[x++][y] = step++;
34. x -= 1;
35. y -= 1;
37. // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
38. while (y >= 0 && matrix[x][y] == "*" && step <= n) matrix[x][y--] = step++;
39. y += 1;
40. x -= 1;
42. // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
43. while (x >= 0 && matrix[x][y] == "*" && step <= n) matrix[x--][y] = step++;
44. x += 1;
45. y += 1;
46. }
48. // 打印螺旋矩阵字符串
49. for (let i = 0; i < m; i++) {
50. console.log(matrix[i].join(" "));
51. }
52. })();

Java算法源码

1. import java.util.Scanner;
2. import java.util.StringJoiner;
4. public class Main {
6. public static void main(String[] args) {
7. Scanner sc = new Scanner(System.in);
9. // 需要在螺旋矩阵中填入 1 ~ n 数字
10. int n = sc.nextInt();
12. // 螺旋矩阵行数
13. int m = sc.nextInt();
15. // 螺旋矩阵列数
16. int k = (int) Math.ceil(n * 1.0 / m);
18. // 螺旋矩阵
19. int[][] matrix = new int[m][k]; // 由于需要填入1~n数字，因此这里未填值的位置值默认初始化为0
21. // 当前要填入的值
22. int step = 1;
24. // 当前要填入的值的位置
25. int x = 0;
26. int y = 0;
28. // 如果填入的值 > n，则停止填值，否则继续填
29. while (step <= n) {
30. // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
31. while (y < k && matrix[x][y] == 0 && step <= n) matrix[x][y++] = step++;
32. // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步
33. y -= 1;
34. // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列
35. x += 1;
37. // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
38. while (x < m && matrix[x][y] == 0 && step <= n) matrix[x++][y] = step++;
39. x -= 1;
40. y -= 1;
42. // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
43. while (y >= 0 && matrix[x][y] == 0 && step <= n) matrix[x][y--] = step++;
44. y += 1;
45. x -= 1;
47. // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
48. while (x >= 0 && matrix[x][y] == 0 && step <= n) matrix[x--][y] = step++;
49. x += 1;
50. y += 1;
51. }
53. // 打印螺旋矩阵字符串
54. for (int i = 0; i < m; i++) {
55. StringJoiner row = new StringJoiner(" ");
56. for (int j = 0; j < k; j++) {
57. if (matrix[i][j] == 0) {
58. row.add("*");
59. } else {
60. row.add(matrix[i][j] + "");
61. }
62. }
63. System.out.println(row);
64. }
65. }
66. }

Python算法源码

1. import math
3. # 输入获取
4. # n 表示需要在螺旋矩阵中填入 1 ~ n 数字
5. # m 表示螺旋矩阵行数
6. n, m = map(int, input().split())
9. # 算法入口
10. def getResult():
11. # k是螺旋矩阵列数
12. k = int(math.ceil(n / m))
14. # 螺旋矩阵
15. matrix = [['*'] * k for _ in range(m)] # 未填值位置默认初始化为*
17. # 当前要填入的值
18. step = 1
20. # 当前要填入的值的位置
21. x = 0
22. y = 0
24. # 如果填入的值 > n，则停止填值，否则继续填
25. while step <= n:
26. # 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
27. while y < k and matrix[x][y] == '*' and step <= n:
28. matrix[x][y] = str(step)
29. step += 1
30. y += 1
32. # 正序填完第x行后，y处于末尾越界位置，因此y需要退一步
33. y -= 1
34. # 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列
35. x += 1
37. # 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
38. while x < m and matrix[x][y] == '*' and step <= n:
39. matrix[x][y] = str(step)
40. step += 1
41. x += 1
43. x -= 1
44. y -= 1
46. # 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
47. while y >= 0 and matrix[x][y] == '*' and step <= n:
48. matrix[x][y] = str(step)
49. step += 1
50. y -= 1
52. y += 1
53. x -= 1
55. # 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
56. while x >= 0 and matrix[x][y] == '*' and step <= n:
57. matrix[x][y] = str(step)
58. step += 1
59. x -= 1
61. x += 1
62. y += 1
64. # 打印螺旋矩阵字符串
65. for i in range(m):
66. print(" ".join(matrix[i]))
69. # 算法调用
70. getResult()

C算法源码

1. #include
2. #include
4. int main() {
5. // n 表示需要在螺旋矩阵中填入 1 ~ n 数字
6. // m 表示螺旋矩阵行数
7. int n, m;
8. scanf("%d %d", &n, &m);
10. // k 表示螺旋矩阵列数
11. int k = (int) ceil(n * 1.0 / m);
13. // 螺旋矩阵
14. int matrix[m][k];
15. for (int i = 0; i < m; i++) {
16. for (int j = 0; j < k; j++) {
17. matrix[i][j] = 0; // 由于需要填入1~n数字，因此这里未填值的位置值默认初始化为0
18. }
19. }
21. // 当前要填入的值
22. int step = 1;
24. // 当前要填入的值的位置
25. int x = 0;
26. int y = 0;
28. // 如果填入的值 > n，则停止填值，否则继续填
29. while (step <= n) {
30. // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
31. while (y < k && matrix[x][y] == 0 && step <= n) matrix[x][y++] = step++;
32. // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步
33. y -= 1;
34. // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列
35. x += 1;
37. // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
38. while (x < m && matrix[x][y] == 0 && step <= n) matrix[x++][y] = step++;
39. x -= 1;
40. y -= 1;
42. // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
43. while (y >= 0 && matrix[x][y] == 0 && step <= n) matrix[x][y--] = step++;
44. y += 1;
45. x -= 1;
47. // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
48. while (x >= 0 && matrix[x][y] == 0 && step <= n) matrix[x--][y] = step++;
49. x += 1;
50. y += 1;
51. }
53. // 打印螺旋矩阵字符串
54. for (int i = 0; i < m; i++) {
55. for (int j = 0; j < k; j++) {
56. if (matrix[i][j] == 0) {
57. printf("*");
58. } else {
59. printf("%d", matrix[i][j]);
60. }
62. if (j < k - 1) {
63. printf(" ");
64. }
65. }
66. puts("");
67. }
69. return 0;
70. }

C++算法源码

1. #include
3. using namespace std;
5. int main() {
6. int n, m;
7. cin >> n >> m;
9. int k = n / m + (n % m ? 1 : 0);
11. int matrix[m][k];
12. for (int i = 0; i < m; i++) {
13. for (int j = 0; j < k; j++) {
14. matrix[i][j] = 0;
15. }
16. }
18. int step = 1;
20. int x = 0;
21. int y = 0;
23. // 如果填入的值 > n，则停止填值，否则继续填
24. while (step <= n) {
25. // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
26. while (y < k && matrix[x][y] == 0 && step <= n) matrix[x][y++] = step++;
27. // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步
28. y -= 1;
29. // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列
30. x += 1;
32. // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
33. while (x < m && matrix[x][y] == 0 && step <= n) matrix[x++][y] = step++;
34. x -= 1;
35. y -= 1;
37. // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
38. while (y >= 0 && matrix[x][y] == 0 && step <= n) matrix[x][y--] = step++;
39. y += 1;
40. x -= 1;
42. // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
43. while (x >= 0 && matrix[x][y] == 0 && step <= n) matrix[x--][y] = step++;
44. x += 1;
45. y += 1;
46. }
48. // 打印螺旋矩阵字符串
49. for (int i = 0; i < m; i++) {
50. for (int j = 0; j < k; j++) {
51. if (matrix[i][j] == 0) {
52. cout << "*";
53. } else {
54. cout << matrix[i][j];
55. }
57. if (j < k - 1) {
58. cout << " ";
59. }
60. }
61. cout << endl;
62. }
64. return 0;
65. }