iT邦幫忙

2021 iThome 鐵人賽

DAY 16
0
自我挑戰組

每日LeetCode解題紀錄系列 第 16

LeetCode解題 Day16

54. Spiral Matrix

https://leetcode.com/problems/spiral-matrix/submissions/


題目解釋

有一個m*n 大小的表格,請用螺旋的順序回傳表格內的值

example

https://i.imgur.com/YY0jLPg.png

解法

不管表格的大小如何,在表格上所謂的螺旋順序,其實都可以看成4個方向的走向

都是從最左上方的位置往右走,接著依序往下、左、上、右...

接著,我們以example2 為範例,分別看4個方向的表格變化:

  • 右: matrix[0][0] -> matrix[0][1] -> matrix[0][2] -> matrix[0][3]
  • 下: matrix[1][3] -> matrix[2][3]
  • 左: matrix[2][2] -> matrix[2][1] -> matrix[2][0]
  • 上: matrix[1][0]

可以發現每個方向只有rowcolmun 有變化,所以我分別寫出4個方向的數字變化

code

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        
        m = len(matrix)
        n = len(matrix[0])
        
        start_i, end_i = 0, m - 1
        start_j, end_j = 0, n - 1
        
        ans = []
        while len(ans) < m * n:

            for j in range(start_j, end_j + 1): #往右
                ans.append(matrix[start_i][j])

            start_i += 1

            if len(ans) < m * n:
                for i in range(start_i, end_i + 1): #往下
                    ans.append(matrix[i][end_j])

                end_j -= 1

            if len(ans) < m * n:
                for j in range(end_j, start_j-1, -1): #往左
                    ans.append(matrix[end_i][j])

                end_i -= 1

            if len(ans) < m * n:
                for i in range(end_i, start_i-1, -1): #往上
                    ans.append(matrix[i][start_j])

                start_j += 1
        
        return ans
              

閒聊

像這種有2維陣列的題目我都覺得很麻煩,有時候都會寫到腦袋空白

原因是什麼我也不確定,可能是和座標一直搞混吧

例如x軸上的座標是(0,0)、(1,0)、(2,0)...
而2維陣列的第一行矩陣則是matrix[0][1]、matrix[0][2]、matrix[0][3]...


上一篇
LeetCode解題 Day15
下一篇
LeetCode解題 Day17
系列文
每日LeetCode解題紀錄30

尚未有邦友留言

立即登入留言