剣指Offer 29.時計回り印刷マトリクス(python)

4397 ワード
lettecode
タイトルリンクタイトル説明:マトリクスを入力し、各数字を外から時計回りに順次印刷します.
例1:
入力:matrix=[[1,2,3],[4,5,6],[7,8,9]]出力:[1,2,3,6,9,8,7,4,5]例2:
入力:matrix=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]出力:[1,2,3,4,8,12,11,10,9,5,6,7]
レイヤ別シミュレーション
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix: return []
        col,row=len(matrix[0]),len(matrix)
        start=0
        res=[]
        while(col>start*2 and row>start*2):
            self.printMatrix(matrix,col,row,start,res)
            start+=1
        return res

    def printMatrix(self,matrix,col,row,start,res):
        endY=row-1-start
        endX=col-1-start
        for i in range(start,endX+1):#        
            res.append(matrix[start][i])
        if endY>start:#    
            for i in range(start+1,endY+1):#        
                res.append(matrix[i][endX])
        if endX>start and endY>start:#      
            for i in range(endX-1,start-1,-1):#        
                res.append(matrix[endY][i])
        if endX>start and endY>start+1:#      
            for i in range(endY-1,start,-1):#        
                res.append(matrix[i][start])

方法1:印刷マトリクスをシミュレートできるパスをシミュレートします.初期位置はマトリクスの左上隅で、初期方向は右方向で、経路が限界を超えたり、前にアクセスした位置に入ったりすると、時計回りに回転して次の方向に入ります.
パスが以前にアクセスした場所に入るかどうかを判断するには、入力マトリクスと同じサイズの補助マトリクスtextit{visited}visitedを使用する必要があります.各要素は、その場所がアクセスされたかどうかを示します.1つの要素がアクセスされると、textit{visited}visitedの対応する場所の要素がアクセスされたとします.
パスが終了したかどうかをどのように判断しますか?マトリクス内の各要素が1回アクセスされるため、パスの長さはマトリクス内の要素の数であり、パスの長さがマトリクス内の要素の数に達すると完全なパスとなり、パスが返されます.
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not 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 = 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]
            if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):
                directionIndex = (directionIndex + 1) % 4
            row += directions[directionIndex][0]
            column += directions[directionIndex][1]
        return order

方法2:レイヤシミュレーションによってマトリクスをいくつかのレイヤと見なすことができ、まず最外層の要素を印刷し、次に最内層の要素を印刷するまで、二次外層の要素を印刷する.
マトリクスを定義するkk番目のレイヤは、kkに最も近い境界距離を持つすべての頂点です.例えば、下図のマトリックスの最外層要素はすべて11層目で、次外層要素はすべて22層目で、残りの要素はすべて33層目です.
[[1,1,1,1,1,1,1],[1,2,2,2,2,2,1],[1,2,3,3,2,1],[1,2,2,2,2,2,1],[1,1,1,1,1,1,1]各層について左上から時計回りの順序で全元素を遍歴した.現在のレイヤの左上隅が(textit{top},textit{left})(top,left)、右下隅が(textit{bottom},textit{right})(bottom,right)にあると仮定し、現在のレイヤの要素を以下の順序で巡回します.
上側の要素を左から右に巡回し、(textit{top},textit{left})(top,left)~(textit{top},textit{right})(top,right)の順になります.
右側の要素を上から下にかけて、(textit{top}+1,textit{right})(top+1,right)~(textit{bottom},textit{right})(bottom,right)の順に巡回します.
もしtextit{left}現在のレイヤの要素を巡回した後、textit{left}leftとtextit{top}topをそれぞれ11ずつ増やし、textit{right}rightとtextit{bottom}bottomをそれぞれ11ずつ減らし、次のレイヤに入ってすべての要素を巡回するまで巡回し続けます.
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return list()
        
        rows, columns = len(matrix), len(matrix[0])
        order = list()
        left, right, top, bottom = 0, columns - 1, 0, rows - 1
        while left <= right and top <= bottom:
            for column in range(left, right + 1):
                order.append(matrix[top][column])
            for row in range(top + 1, bottom + 1):
                order.append(matrix[row][right])
            if left < right and top < bottom:
                for column in range(right - 1, left, -1):
                    order.append(matrix[bottom][column])
                for row in range(bottom, top, -1):
                    order.append(matrix[row][left])
            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
        return order
【MATLAB】AWGNで送信するための関数
【C++】G++コマンド概要