螺旋矩阵问题

力扣54、59

Posted by songjiu on March 10, 2019

很多校招的基础算法题,手撕代码等,还是有必要了解一下的。

问题阐述

问题思考

切割法,类似剥洋葱的感觉,定义四个变量up、down、right、left分别控制切割位置如下图所示:

代码:

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        #画图分割
        if len(matrix)==0:
            return matrix
        up,down,left,right=0,len(matrix),0,len(matrix[0])
        res=[]
        total=len(matrix)*len(matrix[0])
        while up<down and left<right:
            #######################################
            if len(res)==total:
                break
            for i in range(left,right):
                res.append(matrix[up][i])
            up+=1
            #######################################
            if len(res)==total:
                break
            for i in range(up,down):
                res.append(matrix[i][right-1])
            right-=1
            #######################################
            if len(res)==total:
                break
            for i in range(right-1,left-1,-1):
                res.append(matrix[down-1][i])
            down-=1
            #######################################
            if len(res)==total:
                break
            for i in range(down-1,up-1,-1):
                res.append(matrix[i][left])
            left+=1
            ########################################
        return res