本系列為筆者的?Leetcode 刷題記錄，順序為 Hot 100 題官方順序，根據標簽命名，記錄筆者總結的做題思路，附部分代碼解釋和疑問解答。

目錄

01 矩陣置零

方法一：標記數組

方法二：兩個標記變量

02 螺旋矩陣

方法一：模擬

方法二：按層模擬

03 旋轉圖像

方法一：輔助數組

方法二：原地旋轉

方法三：用翻轉代替旋轉

04 搜索二維矩陣 Ⅱ

方法一：直接查找

方法二：二分法

方法三：Z字形查找

---

01 矩陣置零

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {}
};

方法一：標記數組

時間復雜度 O(mn)，空間復雜度 O(m + n)

• 建立兩個數組 row(m) 和 col(n)，存儲 matrix 中行和列的含零情況

• 遍歷數組，判斷行或列含零，執行 matrix[i][j] = 0

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<int> row(m), col(n);for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){if(!matrix[i][j]){row[i] = true;col[j] = true;}}}for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){if(row[i] || col[j]){matrix[i][j] = 0;}}}}
};

① vector<int> row(m), col(n);這倆數組沒有初始化啥的嗎，它們聲明時的默認元素值是多少？

使用?vector<int> row(m)?這樣的語句聲明一個?vector并指定大小時，?vector會自動初始化為指定大小的元素，且每個元素默認初始化為零。

方法二：兩個標記變量

時間復雜度 O(mn)，空間復雜度 O(1)

• 建立兩個標記 flag_col0 和 flag_row0，存儲 matrix 中除第零行和第零列的含零情況

• 遍歷數組，判斷 !matrix[i][0] || !matrix[0][j]，執行 matrix[i][j] = 0

• 第零行和第零列單獨更新

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size(); //一共m行int n = matrix[0].size(); //一共n列int flag_col0 = false, flag_row0 = false;for(int i=0; i<m; ++i){if(!matrix[i][0]) flag_col0 = true;}for(int j=0; j<n; ++j){if(!matrix[0][j]) flag_row0 = true;}//處理大部分元素for(int i=1; i<m; ++i){for(int j=1; j<n; ++j){if(!matrix[i][j]){matrix[i][0] = 0;matrix[0][j] = 0;}}}for(int i=1; i<m; ++i){for(int j=1; j<n; ++j){if(!matrix[i][0] || !matrix[0][j]) {matrix[i][j] = 0;}}}//處理第零行、第零列元素if(flag_col0){for(int i=0; i<m; ++i){matrix[i][0] = 0;}}if(flag_row0){for(int j=0; j<n; ++j){matrix[0][j] = 0;}}}
};

02 螺旋矩陣

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {}
};

方法一：模擬

時間復雜度 O(mn)，空間復雜度 O(mn)

• 建立二維數組 visited(rows, vector<bool>(columns)，存儲矩陣元素的訪問情況

• 遍歷矩陣，判斷 nextRow 和 nextColumn 是否越過邊界

class Solution {
public:static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //向右、下、左、上vector<int> spiralOrder(vector<vector<int>>& matrix) {if (matrix.size() == 0 || matrix[0].size() == 0) return {};int rows = matrix.size(), columns = matrix[0].size(), total = rows * columns;vector<vector<bool>> visited(rows, vector<bool>(columns)); //標記vector<int> order(total); //答案int row = 0, column = 0, dirIndex = 0;for(int i=0; i<total; i++){order[i] = matrix[row][column]; //更新答案visited[row][column] = true; //更新標記int nextRow = row + dirs[dirIndex][0];int nextColumn = column + dirs[dirIndex][1];if(nextRow >= rows || nextRow < 0 || nextColumn >= columns || nextColumn < 0 || visited[nextRow][nextColumn]){dirIndex = (dirIndex + 1) % 4;}row += dirs[dirIndex][0];column += dirs[dirIndex][1];}return order;}
};

① static 意味著變量在程序的生命周期內只會被分配一次，并且在所有對該數組的函數調用中共享同一存儲空間。

② constexpr 用于指定變量值在編譯時就確定下來，它提示編譯器盡量進行優化。

③ {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}每一對元素代表在二維平面上一個方向的坐標變換：

• {0, 1}：代表向右移動 —— 行不變，列加一

• {1, 0}：代表向下移動 —— 行加一，列不變

• {0, -1}：代表向左移動 —— 行不變，列減一

• {-1, 0}：代表向上移動 —— 行減一，列不變

④ vector<bool>(columns) 創建一個布爾向量，大小為 columns，其中每個元素默認初始化為 false。

⑤ vector<vector<bool>>(rows, ...) 表示創建一個這樣的布爾向量的向量，其長度為 rows，即每一行都是一個布爾向量，且每列都是初始化為 false。

⑥ spiral 螺旋形的 constexpr 常量表達式

⑦ 在什么樣的情況下 if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) 中的 nextRow < 0 成立？

由于初始位置是 (0, 0) 且遍歷順序是順時針螺旋，因此 nextRow < 0 通常在當前方向反轉嘗試向上之前使用過的路徑上被訪問時發生。

⑧ 將代碼中涉及 nextRow 和 nextColumn 部分的片段改為如下片段如何？

if((column == (columns - 1)) || (row == (rows - 1)) || (column == 0) || matrix[row + dirs[dirIndex][0]][column + dirs[dirIndex][1]]){dirIndex = (dirIndex + 1) % 4;
}

?matrix[row + dirs[dirIndex][0]][column + dirs[dirIndex][1]]：這種方式不僅增加了代碼復雜度，并且可能由于超出 matrix 的邊界而導致訪問無效內存，出現內存錯誤。

if (column == columns || row == rows || column == -1 || row == -1 ||
row + dirs[dirIndex][0] < 0 || row + dirs[dirIndex][0] >= rows ||
column + dirs[dirIndex][1] < 0 || column + dirs[dirIndex][1] >= columns || 
visited[row + dirs[dirIndex][0]][column + dirs[dirIndex][1]]) {
dirIndex = (dirIndex + 1) % 4;
}

row + dirs[dirIndex][0] < 0：檢查向當前方向移動后，新的行索引是否小于0。這會保持我們不越過上邊界。

row + dirs[dirIndex][0] >= rows：檢查向當前方向移動后，新的行索引是否大于或等于總行數。這會確保我們不越過下邊界。

column + dirs[dirIndex][1] < 0：檢查向當前方向移動后，新的列索引是否小于0。這會確保我們不越過左邊界。

column + dirs[dirIndex][1] >= columns：檢查向當前方向移動后，新的列索引是否大于或等于總列數。這會確保我們不越過右邊界。

方法二：按層模擬

時間復雜度 O(mn)，空間復雜度 O(1)

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {if(matrix.size() == 0 || matrix[0].size() == 0) return {};vector<int> order;int rows = matrix.size(), columns = matrix[0].size();int left = 0, right = columns-1, top = 0, bottom = rows-1;//主打一個遍歷while(left<=right && top<=bottom){for(int column=left; column<=right; ++column) {order.push_back(matrix[top][column]);}for(int row=top+1; row<=bottom; ++row) {order.push_back(matrix[row][right]);}if(left<right && top<bottom){for(int column=right-1; column>=left+1; --column) {order.push_back(matrix[bottom][column]);}for(int row=bottom; row>=top+1; --row) {order.push_back(matrix[row][left]);}}top++;left++;right--;bottom--;}return order;}
};

① 為什么還要第二次判斷 if(left<right && top<bottom) 呢？

在只有一行或者一列剩下時，第二次順時針迭代會導致重復元素被添加到結果中。例如，當只剩下一行時，上面的第二次和第三次迭代（從右向左）會和已經處理的行產生重復。比如：

• 單行（例如，[[1, 2, 3]]）

• 單列（例如，[[1], [2], [3]]）

03 旋轉圖像

class Solution {
public:void rotate(vector<vector<int>>& matrix) {}
};

方法一：輔助數組

時間復雜度 O(n^2)，空間復雜度 O(n^2)

class Solution {
public:void rotate(vector<vector<int>>& matrix) {auto matrix_new = matrix;int n = matrix.size();for(int i=0; i<n; ++i){for(int j=0, j<n; ++j){matrix_new[j][n-1-i] = matrix[i][j];}}return matrix_new;}
};

auto matrix_new = matrix;這行代碼的作用是復制matrix變量的值到一個新的變量matrix_new中，matrix_new的類型與matrix一致。

對于大多數與標準庫相關的容器（如 std::vector），這會創建 matrix 的一個淺拷貝，整體上是深拷貝其內容，而不是僅僅復制指針（如果它是一個復雜數據結構）。

方法二：原地旋轉

時間復雜度 O(n^2)，空間復雜度 O(1)

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for(int x=0; x<n/2; ++x){for(int y=0; y<(n+1)/2; ++y){int flag = matrix[x][y];matrix[x][y] = matrix[n-1-y][x];matrix[n-1-y][x] = matrix[n-1-x][n-1-y];matrix[n-1-x][n-1-y] = matrix[y][n-1-x];matrix[y][n-1-x] = flag;}}}
};

方法三：用翻轉代替旋轉

時間復雜度 O(n^2)，空間復雜度 O(1)

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();for(int x=0; x<n/2; ++x){for(int y=0; y<n; ++y){swap(matrix[x][y], matrix[n-1-x][y]);}}for(int x=0; x<n; ++x){for(int y=0; y<x; ++y){swap(matrix[x][y], matrix[y][x]);}}}
};

04 搜索二維矩陣 Ⅱ

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {}
};

方法一：直接查找

時間復雜度 O(mn)，空間復雜度 O(1)

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(const auto& row: matrix){for(int element: row){if(element == target) return true;}}return false;}
};

方法二：二分法

時間復雜度 O(mlogn)，空間復雜度 O(1)

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(const auto& row: matrix){auto it = lower_bound(row.begin(), row.end(), target);if(it != row.end() && *it == target) return true;}return false;}
};

lower_bound?是一個標準庫函數，位于 <algorithm>?頭文件中，用于在一個已排序的范圍內查找目標值的位置。lower_bound?返回一個迭代器，指向范圍內第一個不小于目標值的元素的位置，如果所有的元素都小于目標值，它將返回指向末尾的迭代器。

注意：使用 lower_bound? 的前提是 row 必須是排序好的，否則結果是不確定的。

方法三：Z字形查找

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int x = 0, y = n-1;while(x < m && y >=0){if(matrix[x][y] == target) return true;else if(matrix[x][y] > target) y--;else x++;}return false;}
};

文章部分代碼來源于力扣（LeetCode）