[LeetCode] #54. Spiral Matrix

-

題目

Given an m x n matrix, return all elements of the matrix in spiral order.

直覺解

構想：

dictionary.target 紀錄接下來要印哪一個 row/ cole，用 dictionary.star 和 ictionary.end 紀錄是從哪裡印到哪裡。

如果 cell 位於 row 和 col 的交叉點，則把該 cell 歸類為 row。以 matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] 為例，cell 的歸類順序是：

  • 上 row: 1, 2, 3

  • 右 col: 6

  • 下 row: 9, 8, 7

  • 左 col: 4

  • 上 row: 5

python 3 實作（失敗）：

class Solution: 

    ans = [] 

    
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]: 

        self.ans = [] 

        if matrix is None: 

            return self.ans 

         

        row = {'target': 0, 'star': 0, 'end': len(matrix[0]), 'reverse': False} 

        col = { 

            'target': len(matrix[0]) - 1,  

            'star': row['target'] + 1,  

            'end': len(matrix) - 1,  

            'reverse': False 

        } 

         

        while row['star'] < row['end'] and col['star'] < col['end']: 

            if row['star'] < row['end']: 

                self.matrix_row(row, col, matrix) 

            if col['star'] < col['end']: 

                self.matrix_col(row, col, matrix) 

        else: 

            if row['star'] < row['end']: 

                self.matrix_row(row, col, matrix) 

            elif col['star'] < col['end']: 

                self.matrix_col(row, col, matrix) 

        return self.ans 

         

    def matrix_row(self, row, col, matrix): 

        if row['reverse'] is False: 

            for num in matrix[row['target']][row['star']:row['end']]: 

                self.ans.append(num) 

            col['target'] = row['end'] - 1 

             

        else: 

            for num in reversed(matrix[row['target']][row['star']:row['end']]): 

                self.ans.append(num) 

             

            col['target'] = row['star'] 

            row['star'] += 1 

            row['end'] -= 1 

        row['reverse'] = not row['reverse'] 

         

    def matrix_col(self, row, col, matrix): 

        if col['reverse'] is False: 

            for i in range(col['star'], col['end']): 

                self.ans.append(matrix[i][col['target']]) 

            row['target'] = col['end'] 

                 

        else: 

            for i in reversed(range(col['star'], col['end'])): 

                self.ans.append(matrix[i][col['target']]) 

            row['target'] = col['star'] 

            col['star'] += 1 

            col['end'] -= 1 

        col['reverse'] = not col['reverse']

Submission Detail

Wrong Answer

Input: [[3],[2]]

Output: [3]

Expected: [3,2]

失敗原因

因為「如果 cell 位於 row 和 col 的交叉點，則把該 cell 歸類為 row。」的設計，造成補東牆破西牆的問題。

原本的 while 迴圈長得比較清爽：

        while row['star'] < row['end'] or col['star'] < col['end']: 

            if row['star'] < row['end']: 

                self.matrix_row(row, col, matrix) 

            if col['star'] < col['end']: 

                self.matrix_col(row, col, matrix)

但原本的 while 迴圈在 Input: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]時，在 row['reverse'] 是 False 時已經窮盡了 matrix 中的所有 cell，但因為 row 的 star 和 end 只會在 row['reverse'] 是 True 時更新，導致重複把 5 放進去 ans 裡。為了避免這個問題，才把 while 迴圈改成現在的樣子。

但現在的 while 迴圈在 Input: [[3],[2]] 時，因為歸類 cell 的方式，導致沒有 col，而只有兩個 row，所以我需要執行兩次 matrix_row 函式，才能完成題目指定的結果。但我的程式碼只允許執行一次 matrix_row 函式（因為沒辦法滿足 col['star'] < col['end'] 的條件）。

構想：

更改 cell 的歸類方式。以 matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] 為例，cell 的 歸類順序是：

  • 上 row: 1, 2, 3

  • 右 col: 6, 9

  • 下 row: 8, 7

  • 左 col: 4

  • 上 row: 5

python 3 實作（失敗）：

class Solution: 

    ans = [] 

 

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]: 

        self.ans = [] 

        if matrix is None: 

            return self.ans 

 

        row = {'target': 0, 'star': 0, 'end': len(matrix[0]), 'reverse': False} 

        col = { 

            'target': len(matrix[0]) - 1, 

            'star': row['target'] + 1, 

            'end': len(matrix), 

            'reverse': False 

        } 

 

        while row['star'] < row['end'] and col['star'] < col['end']: 

            if row['star'] < row['end']: 

                self.matrix_row(row, col, matrix) 

            if col['star'] < col['end']: 

                self.matrix_col(row, col, matrix) 

        return self.ans 

 

    def matrix_row(self, row, col, matrix): 

        if row['reverse'] is False: 

            for num in matrix[row['target']][row['star']:row['end']]: 

                self.ans.append(num) 

            col['target'] = row['end'] - 1 

            col['star'] = row['target'] + 1 

 

        else: 

            for num in reversed(matrix[row['target']][row['star']:row['end']]): 
 
                self.ans.append(num) 

 

            col['target'] = row['star'] 

            col['end'] = row['target'] 

             

        row['reverse'] = not row['reverse'] 

 

    def matrix_col(self, row, col, matrix): 

        if col['reverse'] is False: 

            for i in range(col['star'], col['end']): 

                self.ans.append(matrix[i][col['target']]) 

            row['target'] = col['end'] - 1 

            row['end'] = col['target'] 

 

        else: 

            for i in reversed(range(col['star'], col['end'])): 

                self.ans.append(matrix[i][col['target']]) 

            row['target'] = col['star'] 

            row['star'] = col['target'] + 1 

 

        col['reverse'] = not col['reverse']

Submission Detail

Wrong Answer

Input: [[1]]

Output: []

Expected: [1]

失敗原因

len(matrix) 是 1 的時候，進不去 while 迴圈。

構想：

len(matrix) 是 1 的時候，當作特例處理。

python 3 實作：

class Solution: 

    ans = [] 

 

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]: 

        self.ans = [] 

        if matrix is None: 

            return self.ans 

        if len(matrix) == 1: 

            return matrix[0][:] 

 

        row = {'target': 0, 'star': 0, 'end': len(matrix[0]), 'reverse': False} 

        col = { 

            'target': len(matrix[0]) - 1, 

            'star': row['target'] + 1, 

            'end': len(matrix), 

            'reverse': False 

        } 

 

        while row['star'] < row['end'] and col['star'] < col['end']: 

            if row['star'] < row['end']: 

                self.matrix_row(row, col, matrix) 

            if col['star'] < col['end']: 

                self.matrix_col(row, col, matrix) 

        return self.ans 

 

    def matrix_row(self, row, col, matrix): 

        if row['reverse'] is False: 

            for num in matrix[row['target']][row['star']:row['end']]: 

                self.ans.append(num) 

            col['target'] = row['end'] - 1 

            col['star'] = row['target'] + 1 

 

        else: 

            for num in reversed(matrix[row['target']][row['star']:row['end']]): 
 
                self.ans.append(num) 

 

            col['target'] = row['star'] 

            col['end'] = row['target'] 

             

        row['reverse'] = not row['reverse'] 

 

    def matrix_col(self, row, col, matrix): 

        if col['reverse'] is False: 

            for i in range(col['star'], col['end']): 

                self.ans.append(matrix[i][col['target']]) 

            row['target'] = col['end'] - 1 

            row['end'] = col['target'] 

 

        else: 

            for i in reversed(range(col['star'], col['end'])): 

                self.ans.append(matrix[i][col['target']]) 

            row['target'] = col['star'] 

            row['star'] = col['target'] + 1 

 

        col['reverse'] = not col['reverse']

效能：

Runtime: 20 ms, faster than 99.19% of Python3 online submissions for Spiral Matrix.
Memory Usage: 14.3 MB, less than 27.63% of Python3 online submissions for Spiral Matrix.

感想：這個程式碼，讀起來真是太眼花撩亂了⋯⋯

研究別人的解

來源：Python Easy to Understand beats 98 %

研究重點：怎麼寫得更易讀一點。

別人的 python 3 實作：

class Solution: 

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]: 

        m = len(matrix) 

        n = len(matrix[0]) 

        left = 0  

        right = n-1 

        down  = m-1 

        top = 0 

        direction = 0 

        ans = [] 

        while(left<=right and down>=top): 

             

            if direction ==0: 

                # go right 

                for i in range(left , right+1): 

                    ans.append(matrix[top][i]) 

                top+=1 

            elif direction==1: 

                #go down 

                for j in range(top , down+1): 

                    ans.append(matrix[j][right]) 

                right-=1 

            elif direction ==2: 

                #go left 

                for j in range(right , left-1,-1): 

                    ans.append(matrix[down][j]) 

                down-=1 

            elif direction==3: 

                #go up  

                for j in range(down , top-1 , -1): 

                    ans.append(matrix[j][left]) 

                left+=1 
 
             

            direction= (direction +1)%4 

             

        return ans

效能：

Runtime: 28 ms, faster than 83.67% of Python3 online submissions for Spiral Matrix.
Memory Usage: 14.4 MB, less than 27.56% of Python3 online submissions for Spiral Matrix.

研究感想

direction 的用法好妙！直接用變數存上下左右的範圍，而不是包在 dictionary 裡面，value 取用起來乾淨俐落很多。依照我的寫法，還要特地存一個 target 用來標示要印哪一個 row/ col，但是他只要用上下左右的範圍，就可以直接知道輪到印哪一個 row/ col 了。原來 range 這樣使用就可以把數字由大往小的方向迭代。

他的「上」初始值是 0。我的「上」初始值是 row['target'] + 1，導致 matrix 只有一行的時候就進不去我的 while 迴圈，而需要把只有一行的 matrix 當作特例處理。

我的 while 迴圈裡的 if 其實可以刪掉。

小幅度優化我的 python 實作：為了方便對照，刪掉的地方姑且用 # 註解掉

class Solution: 

    ans = [] 

 

    def spiralOrder(self, matrix: List[List[int]]) -> List[int]: 

        self.ans = [] 

        if matrix is None: 

            return self.ans 

        # if len(matrix) == 1:

            # return matrix[0][:] 

 

        row = {'target': 0, 'star': 0, 'end': len(matrix[0]), 'reverse': False} 

        col = { 

            'target': len(matrix[0]) - 1, 

            'star': 0, 

            'end': len(matrix), 

            'reverse': False 

        } 

 

        while row['star'] < row['end'] and col['star'] < col['end']: 

            # if row['star'] < row['end']: 

                self.matrix_row(row, col, matrix) 

            # if col['star'] < col['end']: 

                self.matrix_col(row, col, matrix) 

        return self.ans 

 

    def matrix_row(self, row, col, matrix): 

        if row['reverse'] is False: 

            for num in matrix[row['target']][row['star']:row['end']]: 

                self.ans.append(num) 

            col['target'] = row['end'] - 1 

            col['star'] = row['target'] + 1 

 

        else: 

            for num in reversed(matrix[row['target']][row['star']:row['end']]): 
 
                self.ans.append(num) 

 

            col['target'] = row['star'] 

            col['end'] = row['target'] 

             

        row['reverse'] = not row['reverse'] 

 

    def matrix_col(self, row, col, matrix): 

        if col['reverse'] is False: 

            for i in range(col['star'], col['end']): 

                self.ans.append(matrix[i][col['target']]) 

            row['target'] = col['end'] - 1 

            row['end'] = col['target'] 

 

        else: 

            for i in reversed(range(col['star'], col['end'])): 

                self.ans.append(matrix[i][col['target']]) 

            row['target'] = col['star'] 

            row['star'] = col['target'] + 1 

 

        col['reverse'] = not col['reverse']

效能：

第一次： Runtime: 24 ms, faster than 95.43% of Python3 online submissions for Spiral Matrix.
Memory Usage: 14 MB, less than 95.18% of Python3 online submissions for Spiral Matrix.

第二次： Runtime: 28 ms, faster than 83.67% of Python3 online submissions for Spiral Matrix.
Memory Usage: 14.4 MB, less than 27.56% of Python3 online submissions for Spiral Matrix.

Comments

Post a Comment

Popular posts from this blog

資料關聯

-
以飲料店的商品種類為例，假設我們現在有飲料和杯子兩種資料。 飲料： id name 1 綠茶 2 紅茶 3 青草茶 杯子： id size 1 500 2 600 3 700 一對一（One to One） 若飲料和杯子是一對一的關係，那麼情況就類似這樣： 綠茶只用 500 cc 的杯子裝 紅茶只用 600 cc 的杯子裝 青草茶只用 700 cc 的杯子裝 一種飲料只有一個尺寸的杯子，而且一個尺寸的杯子也只對應到一種飲料。在這種情況下要建立關聯，有下列兩種方式，擇一即可。這兩種做法在技術上效果是一樣的，不過語意解讀上可能不太一樣。 把關聯欄位加在飲料（語意上，是飲料有杯子這個屬性） 把關聯欄位加在杯子（語意上，是杯子有飲料這個屬性） 把關聯欄位加在飲料的資料表： id name cup_id 1 綠茶 1 2 紅茶 2 3 青草茶 3 把關聯欄位加在杯子的資料表： id size drink_id 1 500 1 2 600 2 3 700 3 一對多（One to Many） 若飲料和杯子是一對多的關係，那麼情況就類似這樣： 綠茶用 500 cc、700 cc 的杯子裝 紅茶只用 600 cc 的杯子裝 一種飲料有許多尺寸的杯子，而且一個尺寸的杯子只對應到一種飲料。 或者是這樣： 綠茶、紅茶、青草茶都只用 500 cc 的杯子裝 一個尺寸的杯子對應到許多種飲料，而且一種飲料只有一個尺寸的杯子。 在這種情況下要建立關聯，一般會選擇加在多的那一邊。如果加在少的那一...
Read more

程式設計相關社群、活動

-
網頁開發 網頁開發雜記 PJCHENder網頁開發咩腳 Backend 台灣 (Backend Tw) Taiwan Backend Group Backend.tw (友善版) Google Chrome Developers 語言 Python Taiwan JavaScript.tw Kotlin： Kraftsman：Coding 職人塾 資安 網路攻防戰 資安解壓縮 Infosec Decompress DEVCORE 如何成為駭客 (資安研討會、社群與網路資源篇) Cymetrics Tech Blog （有胡立大大） 台灣電腦網路危機處理暨協調中心 UCCU Hacker HITCON GIRLS 資安人科技網 個人或公司 資料科學家的工作日常 Ant Yi-Feng Tzeng 偷米騎巴哥 John Liu 的軟體工程思維 Will 保哥的技術交流中心 新加坡商鈦坦科技 Line 的技術部落格 區塊鏈李婷婷 、 FB 、 line 群 管理 TGONetworks 91 敏捷開發之路 技術管理者交流社團 課程 軟體開發學習資訊分享 Udemy 限時免費課程 cs50 中文討論區 Lidemy 鋰學院 商業思維學院 未分類 NEX Foundation 台灣未來基金會 iThome FB Daodu Tech 科技島讀 ∞ Lab 無限大實驗室．金融科技第一站 DevOps Taiwan Chatbot Developers Taiwan 軟體開發的疑難雜症交流區 年會 Hacks In Taiwan 台灣駭客年會 FB 台灣資安大會 cybersec 2021 開源人年會 COSCUP 2021 Python 年會 PyCon 2021 ModernWeb 開發者年會 2021 Javascript 開發者年會 FB: JSDC Taiwan 敏捷年會 Agile Summit 20...
Read more

TCP/ IP 通訊協定

-
為什麼要有通訊協定 不同機器之間，若要能夠溝通的話，需要大家都使用相同的語言。所有人都遵守通訊協定，就不會出現語言隔閡。 什麼是 TCP/ IP 通訊協定 要實現「不同機器之間能夠溝通」，從硬體到軟體，有許多工作要完成。為了讓這份工作比較容易進行，所以將工作拆分成好幾個部分，各自獨立完成；以後若要維護的話，哪個部分有問題，只要維修那個部分就好，不必把所有部分都拿出來檢查，降低維修難度。 至於工作到底要怎麼拆分，不同的模型有不同的建議。OSI（Open System Interconnection）模型切成七層工作，DoD（Department of Defense Model）模型則是切成四層，每一層都有不同的通訊協定。雖然目前實作上通常不是採用 OSI 模型，但為了方便理解「不同機器之間能夠溝通」的機制，通常會用 OSI 模型講解，也會試著將 DoD 模型對應到 OSI 模型。 DoD 模型中有許多通訊協定，不過以 TCP、IP 這兩個通訊協定最具有代表性，所以 DoD 模型又稱為 TCP/ IP 模型。TCP 協定對應到 OSI 模型中的傳送層，IP 協定則是對應到網路層。 TCP、IP 通訊協定負責什麼工作 TCP 協定 發送端的 TCP，和接收端的 TCP，會先進行三向交握，確認彼此能夠順利傳輸資料，才正式開始傳輸資料。 我們可以把要傳輸的資料想像成要郵寄的包裹，郵寄時，包裹會有尺寸或重量的限制，同樣地，傳輸的資料也會有大小的限制。如果資料太大了，TCP 會拆分成小包裹，並且幫每個小包裹編號（以便接收端最後能把小包裹還原成大包裹），並注意是否每一個小包裹都成功送達，若沒有成功送達，TCP 會再補上缺少的小包裹。如果資料太小了，TCP 會幫包裹灌水，以符合大小的下限。 IP 協定 IP 位址就像收件地址，以便確認要將包裹送去哪個主機。IP 位址目前有兩種版本，IPv4 用 32 位元儲存地址，IPv6 用 128 位元儲存地址。所以 IPv6 有比較多的地址可以分配給不同的主機。 IPv4 以 IPv4 而言，位址可以切成兩個部分，第一部分代表 Net ID，第二部分代表 Host ID。相同的 Net ID，代表主機位在相同的 IP 網段，相同 IP 網段的主機之間可以用廣播的方式傳遞資料，而不必透過路由。可以從 N...
Read more