螺旋矩阵

螺旋矩阵

横向遍历m，纵向遍历n-1；横向遍历m-1，纵向遍历n-2；横向遍历m-2，纵向遍历n-3；直到有一方向遍历长度为0时终止。 // time:O(mn) space:O(mn) class Solution: def spiralOrder(self, matrix): if not matrix: return [] cown,cols=len(matrix),len(matrix[0]) judge=1 //1为顺序遍历，-1为逆序遍历 res=[] i,j=0,-1 //初始位置，列为-1，因为代表[0,0]前一个位置 while cown>0 and cols>0: //横向遍历 for _ in range(cols): j+=judge*1 res.append(matrix[i][j] //纵向遍历 for _ in range(cown-1): i+=judge*1 res.append(matrix[i][j]) cown,cols=cown-1,cols-1 judge*=-1 return res

第二种方法：

// time:O(mn) space:O(mn) class Solution: def spiralOrder(self, matrix): if not matrix or not martix[0]: return [] left,right=0,len(matrix[0])-1 top,bottom=0,len(matrix)-1 spiral_path=[] while True: //顶部由左向右 spiral_path.extend(matrix[top][x] for x in range(left,right+1)) top+=1 if top>bottom:break //右部由上到下 spiral_path.extend(matrix[y][right] for y in range(top,bottom+1) right-=1 if left>right:break //底部由右向左 spiral_path.extend(matrix[bottom][x] for x in range(right,left-1,-1)) bottom-=1 if top>bottom:break //左部由下到上 spiral_path.extend(matrix[y][left] for y in range(bottom,top-1)) left+=1 if left>right:break return spiral_path

方法三

// time:O(n) space:O(n) class Solution: def spiralOrder(self, matrix): res=[] if len(matrix)==0:return res rowbegin,rowend,colbegin,colend=0,len(matrix)-1,0,len(matrix[0])-1 while rowbegin<=rowend and colbegin<=colend: //left->right for i in range(colbegin,colend+1): res.append(matrix[rowbegin][i]) rowbegin+=1 //right->bottom for i in range(rowbegin,rowend+1): res.append(matrix[i][colend]) colend-=1 //right->left if rowbegin<=rowend: for i in range(colend,colbegin-1,-1): res.append(matrix[rowend][i]) rowend-=1 //bottom->top if colbegin<=colend: for i in range(rowend,rowbegin-1,-1): res.append(matrix[i][colbegin]) colbegin+=1 return res

螺旋矩阵 II

生成一个 n×n 空矩阵 mat，随后模拟整个向内环绕的填入过程： 定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 tar = n * n；当 num <= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后： 执行 num += 1：得到下一个需要填入的数字。更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。 使用num <= tar而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。 最终返回 mat 即可。 方法一 // time：O(n^2) space:O(n^2) class Solution: def generateMatrix(self, n): left,right,top,bottom=0,n-1,0,n-1 res=[[0 for _ in range(n)] for _ in range(n)] num,target=1,n*n while num<=target: for i in range(left,right+1): res[top][i]=num num+=1 top+=1 for i in range(top,bottom+1): res[i][right]=num num+=1 right-=1 for i in range(right,left-1,-1): res[bottom][i]=num num+=1 bottom-=1 for i in range(bottom,top-1,-1): res[i][left]=num num+=1 left+=1 return res