【算法笔记】螺旋矩阵

⚙️ 基本设定

1. 规则描述

• 生成一个包含 n 个数字，m 行的矩阵。
• 从 1 开始，由左上角顺时针螺旋向内排列。
• 每行数字个数相等，尽可能减少列的数量。
• 数字不够时使用 * 填充。

2. 输入描述

输入两个整数，依次表示 n 和 m。

3. 输出描述

举例输入：9 4 1 2 3 * * 4 9 * 5 8 7 6

🔎 重点解析

1. 列表推导式

list=[expressionforiteminiterableifcondition]

expression表达式计算后的值便是list的每一个元素，一般是对从可迭代对象iterable中取出来的item进行操作。

# 计算列数，必须向上取整保证可以存完cols=Math.ceil(k/n)# 初始化矩阵matrix=[["*"for_inrange(cols)]for_inrange(n)]

有两层推导式：

• 外层[... for _ in range(n)]：创建n行。
• 内层["*" for _ in range(cols)]：每列用"*"填充。
• _是一个合法变量名，一般表示这个值本身只是个占位符，不会被使用，作用域不同两个_也不会冲突，这里用于迭代填入相同的符号"*"。

2. 主逻辑算法

填数算法的核心分为持续填充和改变方向两部分，基于方向控制器用相邻的两个元素控制。

1. 方向控制器directions = [0, 1, 0, -1, 0]：
   • 右：x 不变，y 加 1，对应[0, 1]；
   • 下：x 加 1，y 不变，对应[1, 0]；
   • 左：x 不变，y 减 1，对应[0, -1]；
   • 上：x 减 1，y 不变，对应[-1, 0]。
2. 持续填充：

new_x=start_x+directions[index]new_y=start_y+directions[index+1]

控制index的值就可以改变相邻的一对值，实现方向控制。例如，index = 0时，directions[index]和directions[index + 1]构成[0, 1]，此时new_x不变，new_y加 1，实现向右移动。
3. 改变方向：
new_x和new_y是先驱指针。

if(new_x<0ornew_x>=nornew_y<0ornew_y>=Math.ceil(k/n)ormatrix[new_x][new_y]!="*"):

• 改变方向就是改变index的值，螺旋矩阵是右下左上轮回，根据条件判断，需要改变的时候就改变index。
• 下标从 0 开始，所以=行数或列数时，也是越界。

index=(index+1)%4

让index在 0 - 3 之间循环。

start_x=start_x+directions[index]start_y=start_y+directions[index+1]

此时new_x或new_y是越界状态，要用start_x和start_y拐弯。

3. 输出

1. 手动

foriinrange(n):output_str=""forjinrange(cols):output_str+=matrix[i][j]# 除了每行最后一个，每个数后面都要加空格if(j!=(cols):output_str+=" "print(output_str)

2. 简化

foriinrange(n):print(" ".join(matrix[i][:cols]))

• matrix[i]：获取一行；
• [:cols]：获取前cols个数；
• " ".join(...)：把只包含字符串的可迭代对象中的字符串按照指定分隔符拼接起来。

4. 切片 (Slice) 语法糖

💻 代码实现

importmathasMath# 方向控制器directions=[0,1,0,-1,0]# 列表推导式，输入总数和行数params=[int(x)forxininput().split(" ")]k=params[0]# 总数n=params[1]# 行数cols=Math.ceil(k/n)# 列数# 初始化矩阵，用 * 填充所有位置matrix=[["*"for_inrange(cols)]for_inrange(n)]start_x=0# 行索引start_y=0# 列索引count=1# 当前数字，从 1 开始index=0# 用于确定方向的索引while(True):if(count>k):breakelse:# --- 持续填充 --- #matrix[start_x][start_y]=str(count)# 实则是存放列表的列表，str 类型方便最后拼接字符count+=1new_x=start_x+directions[index]new_y=start_y+directions[index+1]# --- 改变方向 --- ## 分别规定上边界、下边界、左边界、右边界，最后检查是否已经填充数字if(new_x<0ornew_x>=nornew_y<0ornew_y>=colsormatrix[new_x][new_y]!="*"):index=(index+1)%4start_x=start_x+directions[index]start_y=start_y+directions[index+1]else:start_x=new_x start_y=new_yforiinrange(n):print(" ".join(matrix[i][:cols]))