【算法笔记】螺旋矩阵
⚙️ 基本设定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进行操作。# 计算列数必须向上取整保证可以存完colsMath.ceil(k/n)# 初始化矩阵matrix[[*for_inrange(cols)]for_inrange(n)]有两层推导式外层[... for _ in range(n)]创建n行。内层[* for _ in range(cols)]每列用*填充。_是一个合法变量名一般表示这个值本身只是个占位符不会被使用作用域不同两个_也不会冲突这里用于迭代填入相同的符号*。2. 主逻辑算法填数算法的核心分为持续填充和改变方向两部分基于方向控制器用相邻的两个元素控制。方向控制器directions [0, 1, 0, -1, 0]右x 不变y 加 1对应[0, 1]下x 加 1y 不变对应[1, 0]左x 不变y 减 1对应[0, -1]上x 减 1y 不变对应[-1, 0]。持续填充new_xstart_xdirections[index]new_ystart_ydirections[index1]控制index的值就可以改变相邻的一对值实现方向控制。例如index 0时directions[index]和directions[index 1]构成[0, 1]此时new_x不变new_y加 1实现向右移动。3. 改变方向new_x和new_y是先驱指针。if(new_x0ornew_xnornew_y0ornew_yMath.ceil(k/n)ormatrix[new_x][new_y]!*):改变方向就是改变index的值螺旋矩阵是右下左上轮回根据条件判断需要改变的时候就改变index。下标从 0 开始所以行数或列数时也是越界。index(index1)%4让index在 0 - 3 之间循环。start_xstart_xdirections[index]start_ystart_ydirections[index1]此时new_x或new_y是越界状态要用start_x和start_y拐弯。3. 输出手动foriinrange(n):output_strforjinrange(cols):output_strmatrix[i][j]# 除了每行最后一个每个数后面都要加空格if(j!(cols):output_str print(output_str)简化foriinrange(n):print( .join(matrix[i][:cols]))matrix[i]获取一行[:cols]获取前cols个数 .join(...)把只包含字符串的可迭代对象中的字符串按照指定分隔符拼接起来。4. 切片 (Slice) 语法糖语法形式描述示例 (lst [0,1,2,3,4,5])结果seq[start:stop]从start到stop-1的元素 (包含开头不包含结尾)lst[2:5][2, 3, 4]seq[start:]从start到序列末尾的所有元素lst[3:][3, 4, 5]seq[:stop]从序列开头到stop-1的元素lst[:4][0, 1, 2, 3]seq[:]整个序列的浅拷贝lst[:][0,1,2,3,4,5]seq[start:stop:step]从start到stop-1按步长step选取元素lst[1:5:2][1, 3]seq[::step]按步长step选取整个序列的元素lst[::2][0, 2, 4]seq[::-1]步长为负时反向选取元素 (常用于反转序列)lst[::-1][5,4,3,2,1,0]seq[-n:]最后n个元素lst[-3:][3, 4, 5]seq[:-n]除最后n个元素外的所有元素lst[:-2][0, 1, 2, 3]seq[start:stop:-step]步长为负时从start向stop反向选取 (需注意索引方向)lst[4:1:-1][4, 3, 2] 代码实现importmathasMath# 方向控制器directions[0,1,0,-1,0]# 列表推导式输入总数和行数params[int(x)forxininput().split( )]kparams[0]# 总数nparams[1]# 行数colsMath.ceil(k/n)# 列数# 初始化矩阵用 * 填充所有位置matrix[[*for_inrange(cols)]for_inrange(n)]start_x0# 行索引start_y0# 列索引count1# 当前数字从 1 开始index0# 用于确定方向的索引while(True):if(countk):breakelse:# --- 持续填充 --- #matrix[start_x][start_y]str(count)# 实则是存放列表的列表str 类型方便最后拼接字符count1new_xstart_xdirections[index]new_ystart_ydirections[index1]# --- 改变方向 --- ## 分别规定上边界、下边界、左边界、右边界最后检查是否已经填充数字if(new_x0ornew_xnornew_y0ornew_ycolsormatrix[new_x][new_y]!*):index(index1)%4start_xstart_xdirections[index]start_ystart_ydirections[index1]else:start_xnew_x start_ynew_yforiinrange(n):print( .join(matrix[i][:cols]))