平时刷算法题的时候,很多朋友碰到矩阵类题目都会犯难,尤其是螺旋矩阵这道题,看着不难,自己动手写代码就容易乱方向、越界出错。
最近在整理刷题笔记,刚好把这道经典的顺时针螺旋遍历矩阵题目完完整整梳理一遍,每一行代码逐句拆解,就连语法规则、变量含义、写法区别、容易踩的小坑全都讲清楚。
不管是刚入门 Python 刷题,还是一直卡在这道题过不去,静下心跟着慢慢看,全程不跳任何一步,看完就能彻底吃透这道题。
题目介绍
题目大意
给定一个二维整数矩阵,按照顺时针螺旋的顺序,依次取出矩阵里所有元素,最后组合成一维列表进行返回。 简单举例:输入[[1,2,3],[4,5,6],[7,8,9]],最终输出结果为[1,2,3,6,9,8,7,4,5]。
整体解题思路
采用模拟行走的思路完成遍历:
预判下一步位置,越界或者已经走过就自动更换行走方向
完整总代码块
from typing import ListclassSolution:defspiralOrder(self, matrix: List[List[int]]) -> List[int]:ifnot matrix ornot matrix[0]:return list() rows, columns = len(matrix), len(matrix[0]) visited = [[False] * columns for _ in range(rows)] total = rows * columns order = [0] * total directions = [[0, 1], [1, 0], [0, -1], [-1, 0]] row, column = 0, 0 directionIndex = 0for i in range(total): order[i] = matrix[row][column] visited[row][column] = True nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]ifnot (0 <= nextRow < rows and0 <= nextColumn < columns andnot visited[nextRow][nextColumn]): directionIndex = (directionIndex + 1) % 4 row += directions[directionIndex][0] column += directions[directionIndex][1]return order
逐行代码精细讲解
第一行代码
from typing import List
平常我们写普通 Python 脚本用不到这一行,但是在刷力扣算法题的时候必须写上。 typing是 Python 专门用来做类型标注的模块,List用来定义列表格式,后面代码里标注二维数组、一维数组全都要依靠它,不写这一行运行代码会直接出现类型报错。
第二行代码
classSolution:
这是力扣平台固定的代码格式,不是我们自己随意定义的格式,所有算法题目答题都必须创建这个类。 语法上class是 Python 创建类的固定关键字,Solution是统一规定的类名,日常自己写小程序可以不用类,刷题一定要遵守这个格式。
第三行代码
defspiralOrder(self, matrix: List[List[int]]) -> List[int]:
这一行是创建解题核心方法,def是 Python 定义函数和方法的关键字。 第一个参数self属于类方法专属参数,是固定写法不能省略;matrix是我们接收传进来的二维矩阵参数;冒号后面是参数类型提示,代表传入的是二维整数列表;箭头后面代表这个方法最后执行完毕,要返回一个一维整数列表。
第四行代码
ifnot matrix ornot matrix[0]:
做代码编写一定要优先考虑特殊情况,这一行就是用来判断空矩阵的。 第一种情况是传入的矩阵本身为空列表,第二种情况是矩阵存在但是内部没有任何数据,两种任意一种出现,都属于无效矩阵。
第五行代码
return list()
满足上面空矩阵的判断条件之后,直接返回空列表结束本次方法运行,提前终止代码执行,避免后面读取行列数出现索引报错,这也是写代码很重要的习惯。
第六行代码
rows, columns = len(matrix), len(matrix[0])
采用 Python 并行赋值语法,把右侧计算出来的数值,依次赋值给左侧两个变量。 len(matrix)可以算出整个矩阵一共有多少行,赋值给rows;len(matrix[0])取出矩阵第一行,计算出行内元素个数,也就是矩阵总列数,赋值给columns。
第七行代码
visited = [[False] * columns for _ in range(rows)]
创建一个和原矩阵大小完全一致的标记矩阵,里面所有初始值都是False。 作用就是用来记录矩阵里每一个位置有没有被我们遍历取过值,走到哪里就标记哪里,防止重复取值打乱螺旋顺序,列表推导式写法简洁高效,也是矩阵题目常用写法。
第八行代码
total = rows * columns
用行数乘以列数,直接算出整个矩阵里面一共存在多少个元素。 后续循环遍历直接按照总元素数量执行,不多走一步,也不会漏掉任意一个数据。
第九行代码
order = [0] * total
提前创建好一个固定长度的空白结果列表,后续遍历得到的矩阵数值,都会依次存入这个列表当中,最后统一作为最终答案返回。
第十行代码
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
这是整道题最核心的方向数组,提前把四个行走偏移量全部定义好。 依次对应:向右行走、向下行走、向左行走、向上行走,不用重复写大量判断语句切换方向,简化整体代码结构。
第十一行代码
row, column = 0, 0
确定遍历矩阵的起始坐标,矩阵编程默认从左上角位置开始,也就是行下标 0,列下标 0 的位置。
第十二行代码
directionIndex = 0
定义方向索引变量,初始赋值为 0,代表程序一开始启动,默认行走方向为数组里第一个方向,也就是向右走。
第十三行代码
for i in range(total):
开启整体循环,循环执行次数严格等于矩阵所有元素总数,保证每一个数字都能被顺利读取一遍。
第十四行代码
order[i] = matrix[row][column]
遵循赋值语法,把当前坐标在原矩阵中对应的数值,存入结果列表对应的位置当中,完成数值收集。
第十五行代码
visited[row][column] = True
数值读取完成之后,立刻把当前坐标位置标记为已访问,后续行走过程中就不会再次走到这个位置。
第十六行代码
nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]
结合当前行走方向,提前计算出下一步即将走到的坐标位置,提前预判是否能够正常通行。
第十七行代码
ifnot (0 <= nextRow < rows and0 <= nextColumn < columns andnot visited[nextRow][nextColumn]):
条件判断预判下一步位置是否合规,只要出现坐标超出矩阵边界,或者下一步位置已经被走过,就代表当前方向走不通,需要更换方向。
第十八行代码
directionIndex = (directionIndex + 1) % 4
方向走不通时执行这一行代码,让方向索引往后顺延一位,取余 4 是为了让四个方向循环往复切换,不会出现索引超出方向数组范围的情况。
第十九行代码
row += directions[directionIndex][0]
根据最新确定好的行走方向,更新当前所在的行坐标。
第二十行代码
column += directions[directionIndex][1]
同步更新当前所在的列坐标,完成位置移动,进入下一轮循环取值。
第二十一行代码
return order
所有元素全部遍历完成之后,把存放好螺旋顺序数值的结果列表返回,整道题解题逻辑结束。
补充小知识点
容易踩的小坑 一定要优先判断空矩阵,单行矩阵、单列矩阵都要适配,方向顺序绝对不能打乱,一旦顺序颠倒,遍历出来的顺序就会完全错误。
其他替代写法 除了这种模拟走路的写法,还可以采用分层遍历的方式,一圈一圈向内收缩边界取值,逻辑更加直白,两种写法都能顺利通过题目测试,日常刷题两种思路都可以掌握。
变量命名小习惯 代码里用到的rows、columns、visited、directionIndex都是算法题通用简洁命名,见名知意,日常写代码尽量使用这类规范命名,自己回看、他人查看都更容易理解。
结尾文案
这道经典的螺旋矩阵题目拆解就到这里啦,全程没有刻意夸张的语气,都是平时自己刷题总结出来的平实心得,每一行代码都慢慢梳理清楚了。
觉得这份刷题笔记对你有帮助的朋友,不妨顺手点个赞收藏一下,后续还会持续更新这类逐行拆解的算法学习内容,慢慢沉淀,稳步学好 Python 算法~