1.螺旋矩阵（54-中）
题目描述：给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
思路：直接模拟按层填充，定义左右上下边界，循环遍历矩阵。注意：如果是方阵，就可以直接退出循环，但是，如果存在l > r || t > b，则证明最后一次不是圈，是一行或者一列，这时我们可以直接终止循环。
代码：
public List<Integer> spiralOrder(int[][] matrix) { List<Integer> ans = new ArrayList<>(); int m = matrix.length, n = matrix[0].length; int l = 0, r = n - 1, t = 0, b = m - 1; while (l <= r && t <= b) { for (int j = l; j <= r; ++j) { ans.add(matrix[t][j]); } t++; for (int i = t; i <= b; ++i) { ans.add(matrix[i][r]); } r--; if (l > r || t > b) { break; } for (int j = r; j >= l; --j) { ans.add(matrix[b][j]); } b--; for (int i = b; i >= t; --i) { ans.add(matrix[i][l]); } l++; } return ans; }
2.螺旋矩阵II（59-中）
题目描述：生成1-n^2的所有元素，且元素按顺时针螺旋排列的正方形矩阵。
示例：
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路：与上题思路相同，区别是退出循环机制，采用num < tar，这样避免了判断奇偶的情况。
代码：
public int[][] generateMatrix(int n) { int l = 0, r = n - 1, t = 0, b = n - 1; int[][] matrix = new int[n][n]; int num = 1; while (l <= r && t <= b) { for (int j = l; j <= r; ++j) { matrix[t][j] = num++; } t++; for (int i = t; i <= b; ++i) { matrix[i][r] = num++; } r--; for (int j = r; j >= l; --j) { matrix[b][j] = num++; } b--; for (int i = b; i >= t; --i) { matrix[i][l] = num++; } l++; } return matrix; }
3.对角线打印矩阵（498-中）
题目描述：给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
示例：
输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,4,7,5,3,6,8,9]
思路：两种方向的变更，右上到左下，依次交换方向，将结果加入数组。流程如下：
- 确定循环次数，即方向变更的次数 m + n - 1
- 从0开始，偶数次数为右上，奇数次数为右下（通过取余实现）
- 最后确定两个方向具体实现，比如右上方向，设横坐标x， 纵坐标y，一般变化（x--, y++），但是注意边界处理，即上图中1 - 2, 3 - 6，对应不同的边界处理。左下方向类似。具体见代码
代码：
class Solution { public int[] findDiagonalOrder(int[][] mat) { int rowLength = mat.length; int colLength = mat[0].length; int[] ans = new int[rowLength * colLength]; int loop = rowLength + colLength - 1; int x = 0; int y = 0; int index = 0; for (int i = 0; i < loop; i++) { if (i % 2 == 0) { while (x >= 0 && y < colLength) { ans[index++] = mat[x][y]; x--; y++; } if (y < colLength) { // 对应1-2边界 x++; } else { // 对应3-6边界，ps：需要将上一步while中的x和y位置进行修正(x加1, y不变) x += 2; y--; } } else { while (x < rowLength && y >= 0) { ans[index++] = mat[x][y]; x++; y--; } if (x < rowLength) { // 对应4-7边界 y++; } else { // 对应8-9边界 x--; y += 2; } } } return ans; } }
4.旋转图像（48-中）
题目描述：给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
思路：
法1：直接模拟旋转，可以看成一圈一圈的移动。注意：内层循环，为了避免奇数情况，每一圈可能有一个不移动，我们对n进行加1，可以自行举例n = 2 和 n = 3的情况。
法2：先水平翻转，然后主对角线翻转。
代码：
// 代码1 public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n / 2; i++) { for (int j = 0; j < (n + 1) / 2; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[n - j - 1][i]; matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]; matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]; matrix[j][n - i - 1] = tmp; } } } // 代码2 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; } } }
5.搜索二维矩阵（74-中）
题目描述：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
思路：本题关键解题关键是矩阵有序，我们可以从右上角或者左下角出发，缩小数据搜索范围，遍历寻找目标值。
以右上角为例，当前遍历左边的元素比当前值小，当前遍历下边的元素比当前值大。
最优解为二分查找：本题中行尾和行首连接，也具有单调性，故可将二维矩阵转成一维矩阵去做。
代码：
// 直接搜索，时间复杂度：O(m + n) public boolean searchMatrix(int[][] matrix, int target) { int i = 0, j = matrix[0].length - 1; while (i < matrix.length && j > -1) { if (matrix[i][j] == target) return true; else if (matrix[i][j] > target) { j--; } else { i++; } } return false; } // 二分查找，时间复杂度：O(log(mn)) public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int i = 0, j = m * n - 1; while (i < j) { int mid = i + ((j - i) >> 1); if (matrix[mid / n][mid % n] < target) { i = mid + 1; } else { j = mid; } } return matrix[i / n][i % n] == target; }
6.搜索二维矩阵II（240-中）
题目描述：在有序矩阵中寻找指定数值。
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例：
输入：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
思路：直接搜索基本思路同上。但是二分查找则不同，上题我们首先在第一列小于目标值的第一个数，然后再查找目标行，但是由于本题数据排布整体不是严格单调的！
利用有序的性质，我们可以一行一行的进行二分查找（也可以一列一列的）
- 当某一行的第一个元素都大于target了，那么当前行和之后的行都不用考虑了
- 如果当前行的最后一个元素小于target，当前行排除，直接进入下一行。
代码：
// 直接搜索，时间复杂度：O(m + n) public boolean searchMatrix(int[][] matrix, int target) { int i = 0, j = matrix[0].length - 1; while (i < matrix.length && j > -1) { if (matrix[i][j] == target) return true; else if (matrix[i][j] > target) { j--; } else { i++; } } return false; } // 二分查找，时间复杂度：O(mlogn) public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; for (int i = 0; i < m; ++i) { if (matrix[i][0] > target) { break; } if (matrix[i][n - 1] < target) { continue; } int col = binarySearch(matrix[i], target); if (col != -1) { return true; } } return false; } // 二分查找目标值的索引(类似源码) public int binarySearch(int[] arr, int target) { int i = 0, j = arr.length - 1; while (i <= j) { int mid = (i + j) >>> 1; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { i = mid + 1; } else { j = mid - 1; } } return -1; }
7.矩阵置零（73-中）
题目描述：给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法（在函数输入矩阵上直接修改）。进阶：
- 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个仅使用常量空间的解决方案吗？
示例：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]
思路：本题的关键点：如果在输入矩阵上原地修改把行列修改成了 0，那么再遍历到 0 的时候就不知道是原本数组中的 0 还是我们修改得到的 0。所有的解法都是为了解决该问题。
方案1：遍历两遍矩阵，第一遍记录哪些行哪些列有0，第二遍置0。使用两个set进行记录，空间复杂度O(m + n)
方案2：核心：将第一行和第一列作为标志位，为了避免是由于第一行和第一列本来就有0造成的置0，我们需要对第一行第一列单独进行判断，只需要加两个boolean类型变量进行判断即可。
对于方案2优化，直接使用一个标志位，简化代码，但是不如两个标志位好理解。你可能会说一个不是造成了覆盖吗（原先第一个行某个位置不是0，现在是0）。
假设该列没有0，那么第一行对应位置一定不是0，如果是0，那么可能是本身，也可能是下边0导致修改，如何区别呢？正序置0我们没有办法区别，逆序置0即使是覆盖，那么该位置最终也一定是0。
代码：
// 空间复杂度：O(m + n) public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; Set<Integer> rowZero = new HashSet<>(); Set<Integer> colZero = new HashSet<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == 0) { rowZero.add(i); colZero.add(j); } } } for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (rowZero.contains(i) || colZero.contains(j)) { matrix[i][j] = 0; } } } } // 标记法，空间复杂度：O(1) public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean row0Flag = false; boolean col0Flag = false; for (int j = 0; j < n; ++j) { if (matrix[0][j] == 0) { row0Flag = true; break; } } for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) { col0Flag = 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) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (row0Flag) { for (int j = 0; j < n; ++j) { matrix[0][j] = 0; } } if (col0Flag) { for (int i = 0; i < m; ++i) { matrix[i][0] = 0; } } } // 代码优化：一个标志 public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean col0Flag = false; for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) col0Flag = true; for (int j = 1; j < n; ++j) { if (matrix[i][j] == 0) { matrix[i][0] = matrix[0][j] = 0; } } } for (int i = m - 1; i >= 0; --i) { for (int j = n - 1; j >= 1; --j) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } if (col0Flag) matrix[i][0] = 0; } }
