專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

2024開放原子開發者大會于20日至21日在武漢圓滿舉行，工業和信息化部負責人宣布了一項重要數據：我國軟件開發者群體規模已歷史性突破940萬大關，其中武漢地區有40萬。

我國已經成為全球開源參與者數量排名第二，增長速度最快的國家，開源鴻蒙生態設備超過了10億臺，引發大量關注。據了解，目前已有超過70家單位加入開源鴻蒙生態，超過8100人參與代碼貢獻，貢獻代碼超過1.2億行。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第54題：螺旋矩陣。

問題描述

來源：LeetCode第54題

難度：中等

給你一個 m 行 n 列的矩陣 matrix ，請按照 順時針螺旋順序 ，返回矩陣中的所有元素。

示例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]

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

問題分析

這題是讓順時針螺旋順序返回矩陣中的所有元素，我們可以直接模擬， 從外到內一圈一圈的打印矩陣中的元素 ，需要使用4個變量來記錄訪問的位置，直到全部元素都訪問完為止，如下圖所示。

這里還要注意上下左右四個方向訪問的邊界，哪些是開區間哪些是閉區間，代碼如下。

JAVA：

public List   spiralOrder (int[][] matrix)  {     List
         
  ans =  new ArrayList<>();      int n = matrix.length, m = matrix[ 0].length;      int up =  0, down = n -  1, left =  0, right = m -  1;      int total = m * n; // 總的元素個數      while (ans.size() < total) {          // 上面，從左往右打印，左閉右閉區間[left,right]          for ( int i = left; i <= right && ans.size() < total; i++)             ans.add(matrix[up][i]);          // 右邊，從上往下打印，上開下開區間(up,down)          for ( int i = up +  1; i <= down -  1 && ans.size() < total; i++)             ans.add(matrix[i][right]);          // 下邊，從右往左打印，右閉左閉區間[right,left]          for ( int i = right; i >= left && ans.size() < total; i--)             ans.add(matrix[down][i]);          // 左邊，從下往上打印，下開上開區間(down,up)          for ( int i = down -  1; i >= up +  1 && ans.size() < total; i--)             ans.add(matrix[i][left]);         left++;         right--;         up++;         down--;     }      return ans; }

C++：

public:     vector

  spiralOrder(vector

 > &matrix) {         vector

  ans;         int n = matrix.size(), m = matrix[0].size();         int up = 0, down = n - 1, left = 0, right = m - 1;         int total = m * n;// 總的元素個數         while (ans.size() < total) {             // 上面，從左往右打印，左閉右閉區間[left,right]             for (int i = left; i <= right && ans.size() < total; i++)                 ans.push_back(matrix[up][i]);             // 右邊，從上往下打印，上開下開區間(up,down)             for (int i = up + 1; i <= down - 1 && ans.size() < total; i++)                 ans.push_back(matrix[i][right]);             // 下邊，從右往左打印，右閉左閉區間[right,left]             for (int i = right; i >= left && ans.size() < total; i--)                 ans.push_back(matrix[down][i]);             // 左邊，從下往上打印，下開上開區間(down,up)             for (int i = down - 1; i >= up + 1 && ans.size() < total; i--)                 ans.push_back(matrix[i][left]);             left++;             right--;             up++;             down--;         }         return ans;     }

Python：

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:     ans = []     n, m = len(matrix), len(matrix[0])     up, down, left, right = 0, n - 1, 0, m - 1     total = m * n  # 總的元素個數     while len(ans) < total:         # 上面，從左往右打印，左閉右閉區間[left,right]         for i in range(left, right + 1):             ans.append(matrix[up][i])         # 右邊，從上往下打印，上開下閉區間(up,down]         for i in range(up + 1, down + 1):             ans.append(matrix[i][right])         # 上下重疊就終止         if up == down or left == right: break         # 下邊，從右往左打印，右開左閉區間(right,left]         for i in range(right - 1, left - 1, -1):             ans.append(matrix[down][i])         # 左邊，從下往上打印，下開上開區間(down,up)         for i in range(down - 1, up, -1):             ans.append(matrix[i][left])         left += 1         right -= 1         up += 1         down -= 1     return ans

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。