1、73. 矩陣置零

給定一個?m x n 的矩陣，如果一個元素為 0 ，則將其所在行和列的所有元素都設為 0 。請使用 原地 算法。

示例 1：

輸入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
輸出：[[1,0,1],[0,0,0],[1,0,1]]

// 將第一行第一列作為標記位
class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length,n = matrix[0].length;boolean mflag = false,nflag = false;// 記錄標記位是否出現過0，因為此時不記錄，后面若是被覆蓋就不準了for(int i = 0;i < m;i++) {if(matrix[i][0] == 0) {mflag = true;break;}}for(int i = 0;i < n;i++) {if(matrix[0][i] == 0) {nflag = true;break;}}// 讓標記位變零for(int i = 1;i < m;i++) {for(int j = 1;j < n;j++) {if(matrix[i][j] == 0) {// 將該元素所在行列的標記位設為零matrix[i][0] = matrix[0][j] = 0;}}}// 根據已修改過的標記位修改矩陣for(int i = 1;i < m;i++) {for(int j = 1;j < n;j++) {// 根據標記位，將對應行列除標記位外全部涂為0if(matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 0;}}}// 根據之前記錄的標記位進行涂改if(mflag) {for(int i = 0;i < m;i++) {matrix[i][0] = 0;}}if(nflag) {for(int i = 0;i < n;i++) {matrix[0][i] = 0;}}}
}

?2、54. 螺旋矩陣

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

示例 1：

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[1,2,3,6,9,8,7,4,5]

// 一道考驗邊界判斷的題
class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> ans = new ArrayList<>();if (matrix == null || matrix.length == 0) return ans;int top = 0, bottom = matrix.length - 1;int left = 0, right = matrix[0].length - 1;while (top <= bottom && left <= right) {// 1. 左上 → 右上for (int i = left; i <= right; i++) {ans.add(matrix[top][i]);}top++;// 2. 右上 → 右下for (int i = top; i <= bottom; i++) {ans.add(matrix[i][right]);}right--;// 檢測是否還有空間放下新的元素// 3. 右下 → 左下 (需要檢查是否還有行)if (top <= bottom) {for (int i = right; i >= left; i--) {ans.add(matrix[bottom][i]);}bottom--;}// 4. 左下 → 左上 (需要檢查是否還有列)if (left <= right) {for (int i = bottom; i >= top; i--) {ans.add(matrix[i][left]);}left++;}}return ans;}
}

3、48. 旋轉圖像

給定一個 n?×?n 的二維矩陣?matrix 表示一個圖像。請你將圖像順時針旋轉 90 度。

你必須在?原地 旋轉圖像，這意味著你需要直接修改輸入的二維矩陣。請不要 使用另一個矩陣來旋轉圖像。

示例 1：

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[[7,4,1],[8,5,2],[9,6,3]]

// 數學是很重要的工具 多看一些數學推論即可，也不需要多么深耕
class Solution {public void rotate(int[][] matrix) {int n = matrix.length;// 水平翻轉for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < n; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[n - i - 1][j];matrix[n - i - 1][j] = temp;}}// 主對角線翻轉for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}}
}

4、240. 搜索二維矩陣 II

編寫一個高效的算法來搜索?m?x?n?矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性：

• 每行的元素從左到右升序排列。
• 每列的元素從上到下升序排列。

示例 1：

輸入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
輸出：true

// 貪心算法的用處之一
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int x = 0, y = n - 1;while (x < m && y >= 0) {if (matrix[x][y] == target) {return true;}if (matrix[x][y] > target) {--y;} else {++x;}}return false;}
}