(新卷,100分)- 螺旋数字矩阵（Java JS Python C）

(新卷,100分)- 螺旋数字矩阵（Java & JS & Python & C）

题目描述

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

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

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

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

输入描述

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

输出描述

符合要求的唯一矩阵

用例

题目解析

本题需要我们将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算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { // n 表示需要在螺旋矩阵中填入 1 ~ n 数字 // m 是螺旋矩阵行数 const [n, m] = (await readline()).split(" ").map(Number); // k 是螺旋矩阵列数 const k = Math.ceil(n / m); // 螺旋矩阵，未填值位置默认值"*" const matrix = new Array(m).fill(0).map(() => new Array(k).fill("*")); // 当前要填入的值 let step = 1; // 当前要填入的值的位置 let x = 0; let y = 0; // 如果填入的值 > n，则停止填值，否则继续填 while (step <= n) { // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (y < k && matrix[x][y] == "*" && step <= n) matrix[x][y++] = step++; // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步 y -= 1; // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列 x += 1; // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (x < m && matrix[x][y] == "*" && step <= n) matrix[x++][y] = step++; x -= 1; y -= 1; // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (y >= 0 && matrix[x][y] == "*" && step <= n) matrix[x][y--] = step++; y += 1; x -= 1; // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (x >= 0 && matrix[x][y] == "*" && step <= n) matrix[x--][y] = step++; x += 1; y += 1; } // 打印螺旋矩阵字符串 for (let i = 0; i < m; i++) { console.log(matrix[i].join(" ")); } })();

Java算法源码

import java.util.Scanner; import java.util.StringJoiner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 需要在螺旋矩阵中填入 1 ~ n 数字 int n = sc.nextInt(); // 螺旋矩阵行数 int m = sc.nextInt(); // 螺旋矩阵列数 int k = (int) Math.ceil(n * 1.0 / m); // 螺旋矩阵 int[][] matrix = new int[m][k]; // 由于需要填入1~n数字，因此这里未填值的位置值默认初始化为0 // 当前要填入的值 int step = 1; // 当前要填入的值的位置 int x = 0; int y = 0; // 如果填入的值 > n，则停止填值，否则继续填 while (step <= n) { // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (y < k && matrix[x][y] == 0 && step <= n) matrix[x][y++] = step++; // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步 y -= 1; // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列 x += 1; // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (x < m && matrix[x][y] == 0 && step <= n) matrix[x++][y] = step++; x -= 1; y -= 1; // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (y >= 0 && matrix[x][y] == 0 && step <= n) matrix[x][y--] = step++; y += 1; x -= 1; // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (x >= 0 && matrix[x][y] == 0 && step <= n) matrix[x--][y] = step++; x += 1; y += 1; } // 打印螺旋矩阵字符串 for (int i = 0; i < m; i++) { StringJoiner row = new StringJoiner(" "); for (int j = 0; j < k; j++) { if (matrix[i][j] == 0) { row.add("*"); } else { row.add(matrix[i][j] + ""); } } System.out.println(row); } } }

Python算法源码

import math # 输入获取 # n 表示需要在螺旋矩阵中填入 1 ~ n 数字 # m 表示螺旋矩阵行数 n, m = map(int, input().split()) # 算法入口 def getResult(): # k是螺旋矩阵列数 k = int(math.ceil(n / m)) # 螺旋矩阵 matrix = [['*'] * k for _ in range(m)] # 未填值位置默认初始化为* # 当前要填入的值 step = 1 # 当前要填入的值的位置 x = 0 y = 0 # 如果填入的值 > n，则停止填值，否则继续填 while step <= n: # 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值 while y < k and matrix[x][y] == '*' and step <= n: matrix[x][y] = str(step) step += 1 y += 1 # 正序填完第x行后，y处于末尾越界位置，因此y需要退一步 y -= 1 # 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列 x += 1 # 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值 while x < m and matrix[x][y] == '*' and step <= n: matrix[x][y] = str(step) step += 1 x += 1 x -= 1 y -= 1 # 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值 while y >= 0 and matrix[x][y] == '*' and step <= n: matrix[x][y] = str(step) step += 1 y -= 1 y += 1 x -= 1 # 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值 while x >= 0 and matrix[x][y] == '*' and step <= n: matrix[x][y] = str(step) step += 1 x -= 1 x += 1 y += 1 # 打印螺旋矩阵字符串 for i in range(m): print(" ".join(matrix[i])) # 算法调用 getResult()

C算法源码

#include <stdio.h> #include <math.h> int main() { // n 表示需要在螺旋矩阵中填入 1 ~ n 数字 // m 表示螺旋矩阵行数 int n, m; scanf("%d %d", &n, &m); // k 表示螺旋矩阵列数 int k = (int) ceil(n * 1.0 / m); // 螺旋矩阵 int matrix[m][k]; for (int i = 0; i < m; i++) { for (int j = 0; j < k; j++) { matrix[i][j] = 0; // 由于需要填入1~n数字，因此这里未填值的位置值默认初始化为0 } } // 当前要填入的值 int step = 1; // 当前要填入的值的位置 int x = 0; int y = 0; // 如果填入的值 > n，则停止填值，否则继续填 while (step <= n) { // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (y < k && matrix[x][y] == 0 && step <= n) matrix[x][y++] = step++; // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步 y -= 1; // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列 x += 1; // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (x < m && matrix[x][y] == 0 && step <= n) matrix[x++][y] = step++; x -= 1; y -= 1; // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (y >= 0 && matrix[x][y] == 0 && step <= n) matrix[x][y--] = step++; y += 1; x -= 1; // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值 while (x >= 0 && matrix[x][y] == 0 && step <= n) matrix[x--][y] = step++; x += 1; y += 1; } // 打印螺旋矩阵字符串 for (int i = 0; i < m; i++) { for (int j = 0; j < k; j++) { if (matrix[i][j] == 0) { printf("*"); } else { printf("%d", matrix[i][j]); } if (j < k - 1) { printf(" "); } } puts(""); } return 0; }