Stefan Pochmann 的上帝之手（2）旋轉(zhuǎn)打印矩陣

螺旋矩陣

給定一個包含 m x n 個元素的矩陣（m 行, n 列）迁杨，請按照順時針螺旋順序就珠，返回矩陣中的所有元素蛉威。

示例 1:

輸入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
輸出: [1,2,3,6,9,8,7,4,5]

示例 2:

輸入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]

普通寫法1 （18行）

鏈接：https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/
模擬螺旋矩陣的路徑仿荆，初始位置是矩陣的左上角，初始方向是向右鲤桥，當路徑超出界限或者進入之前訪問過的位置時揍拆，則順時針旋轉(zhuǎn)，進入下一個方向芜壁。判斷路徑是否進入之前訪問過礁凡，需要使用一個與輸入矩陣大小相同的輔助矩陣 $\textit{visited}$ 高氮，其中的每個元素表示該位置是否被訪問過慧妄。當一個元素被訪問時，將 $\textit{visited}$ 中的對應(yīng)位置的元素設(shè)為已訪問剪芍。

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 （17行）

可以將矩陣看成若干層塞淹，首先輸出最外層的元素，其次輸出次外層的元素罪裹，直到輸出最內(nèi)層的元素饱普。定義矩陣的第 k 層是到最近邊界距離為 k 的所有頂點。例如状共，下圖矩陣最外層元素都是第1層套耕，次外層元素都是第2層，剩下的元素都是第3層峡继。

[[1, 1, 1, 1, 1, 1, 1],
 [1, 2, 2, 2, 2, 2, 1],
 [1, 2, 3, 3, 3, 2, 1],
 [1, 2, 2, 2, 2, 2, 1],
 [1, 1, 1, 1, 1, 1, 1]]

對于每層冯袍，從左上方開始以順時針的順序遍歷所有元素。假設(shè)當前層的左上角位于 $(\textit{top}, \textit{left})$ 碾牌，右下角位于 $(\textit{bottom}, \textit{right})$ 康愤，按照如下順序遍歷當前層的元素。

從左到右遍歷上側(cè)元素舶吗，依次為 $(\textit{top}, \textit{left})$ 到 $(\textit{top}, \textit{right})$ 征冷。
從上到下遍歷右側(cè)元素，依次為 $(\textit{top} + 1, \textit{right})$ 到 $(\textit{bottom}, \textit{right})$ 誓琼。
如果 $\textit{left} < \textit{right}$ 且 $\textit{top} < \textit{bottom}$ 检激，則從右到左遍歷下側(cè)元素，依次為 $(\textit{bottom}, \textit{right} - 1)$ 到 $(\textit{bottom}, \textit{left} + 1)$
以及從下到上遍歷左側(cè)元素腹侣，依次為 $(\textit{bottom}, \textit{left})$ 到 $(\textit{top} + 1, \textit{left})$ 叔收。
遍歷完當前層的元素之后，將 $\textit{left}$ 和 $\textit{top}$ 分別增加1筐带，將 $\textit{right}$ 和 $\textit{bottom}$ 分別減少1今穿，進入下一層繼續(xù)遍歷，直到遍歷完所有元素為止伦籍。

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

普通寫法3（19行）

鏈接：https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a?toCommentId=1128425
來源：爬渡梗客網(wǎng)
模擬魔方逆時針旋轉(zhuǎn)的方法腮出，一直做取出第一行的操作。例如 :

1 2 3
4 5 6
7 8 9

輸出并刪除第一行后芝薇，再進行一次逆時針旋轉(zhuǎn)胚嘲，就變成：

6 9
5 8
4 7

繼續(xù)重復(fù)上述操作即可。

class Solution:
    # matrix類型為二維列表洛二，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        result = []
        while(matrix):
            result+=matrix.pop(0)
            if not matrix or not matrix[0]:
                break
            matrix = self.turn(matrix)
        return result
    def turn(self,matrix):
        num_r = len(matrix)
        num_c = len(matrix[0])
        newmat = []
        for i in range(num_c):
            newmat2 = []
            for j in range(num_r):
                newmat2.append(matrix[j][i])
            newmat.append(newmat2)
        newmat.reverse()
        return newmat

上帝之手（1行）

思路與解法3一樣馋劈，每次取第一行并逆時針旋轉(zhuǎn)，直到矩陣為空晾嘶。

def spiralOrder(self, matrix):
        return matrix and list(matrix.pop(0)) + self.spiralOrder(zip(*matrix)[::-1])

技巧1：zip語句將矩陣按列重組妓雾，*matrix表示元組。zip(*matrix)將從第一列開始排到最后一列垒迂，[::-1]表示倒序械姻，zip(*matrix)[::-1]表示matrix逆時針旋轉(zhuǎn)一次。例子：

matrix = [[1, 2, 3],
          [4, 5, 6]]

zip(*matrix)

[(1, 4), 
 (2, 5),
 (3, 6)]

zip(*matrix)[::-1]

[(3, 6), 
 (2, 5), 
 (1, 4)]

技巧2：遞歸調(diào)用函數(shù)自身机断。這一步減少了代碼量楷拳，代價是使用堆棧，運行會變慢吏奸。