[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

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more