矩阵
48.旋转图像
难度：⭐️⭐️⭐️
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
解法一 原地旋转
顺时针循环，每次将4个位置的值轮换。为了防止旋转之后恢复原状，只需要遍历1/2。
原地旋转
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 temp = 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] = temp;
}
}
}
解法二 翻转
先水平翻转，再沿主对角线翻转。
两次翻转
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;
}
}
}
54.螺旋矩阵
难度：⭐️⭐️⭐️
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 10
- -100 <= matrix[i][j] <= 100
解法一 模拟 用额外 m*n 的矩阵记录特定每个位置是否被访问过。题目没有要求不能修改原始矩阵，也可以直接修改原始矩阵。对于移动的方向，可以用一个二维数组来记录，可以简化写法。
直接访问
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
int m = matrix.length;
int n = matrix[0].length;
int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int index = 0;
int r = 0;
int c = 0;
while (list.size() < m * n) {
list.add(matrix[r][c]);
matrix[r][c] = -999;
int nextRow = r + direction[index][0];
int nextColumn = c + direction[index][1];
if (nextRow < 0 || nextRow >= m || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] == -999) {
// 换向
index = (index + 1) % 4;
}
r += direction[index][0];
c += direction[index][1];
}
return list;
}
解法二 按层遍历
记录上下左右边界，在循环中向4个方向移动。
循环按层遍历
public List<Integer> spiralOrder(int[][] matrix) {
int left = 0;
int top = 0;
int right = matrix[0].length - 1;
int bottom = matrix.length - 1;
List<Integer> list = new ArrayList<>();
int count = matrix.length * matrix[0].length;
while (true) {
// right
for (int i = left; i <= right; i++) {
list.add(matrix[top][i]);
}
if (++top > bottom) break;
// bottom
for (int i = top; i <= bottom; i++) {
list.add(matrix[i][right]);
}
if (--right < left) break;
// left
for (int i = right; i >= left; i--) {
list.add(matrix[bottom][i]);
}
if (--bottom < top) break;
// up
for (int i = bottom; i >= top; i--) {
list.add(matrix[i][left]);
}
if (++left > right) break;
}
return list;
}
73. 矩阵置零
难度：⭐️⭐️⭐️
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
解法一 标记数组
用 2 个数组，分别记录行和列的数组中是否有 0，第一次遍历填充标记数组，第二次遍历，对矩阵中元素置零。
标记数组
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
boolean[] r = new boolean[row];
boolean[] c = new boolean[col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0) {
r[i] = true;
c[j] = true;
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (r[i] || c[j]) {
matrix[i][j] = 0;
}
}
}
}
74.搜索二维矩阵
难度：⭐️⭐️⭐️
给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
你必须编写一个时间复杂度为 O(log(m * n)) 的解决方案。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -104 <= matrix[i][j], target <= 104
解法一 2 次二分查找
第一次在第 0 列中从上到下搜索，找到第一个小于 target 的行，第二次在找到的行中搜索。注意的是，第一次二分查找边界需要向上取整。
时间复杂度：O(log(mn))
空间复杂度：O(1)
2次二分查找
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
if (target < matrix[0][0] || target > matrix[m -1][n - 1]) {
return false;
}
int start = 0;
int end = m - 1;
int row = 0;
while (start < end) {
int mid = start + (end - start + 1) / 2;
if (matrix[mid][0] == target) {
return true;
} else if (target < matrix[mid][0]){
end = mid - 1;
} else {
start = mid;
}
}
row = start;
start = 0;
end = n - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target == matrix[row][mid]) {
return true;
} else if (target < matrix[row][mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
}
解法二 一次二分查找
由于每一行的行首元素大于上一行的行尾元素，因此按行遍历，就可以得到一个长度为 m*n 的有序数组，直接使用二分查找，取中间位置时，恢复成坐标即可。
时间复杂度：O(log(mn))
空间复杂度：O(1)
1次二分查找
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int start = 0;
int end = m * n - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
int row = mid / n;
int col = mid % n;
if (target == matrix[row][col]) {
return true;
} else if (target < matrix[row][col]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
}
解法三 二叉搜索树
从右上角或者左上角看，矩阵是一个二叉搜索树，直接按二叉搜索树查找即可。 这种解法的时间复杂度不符合题目要求。
时间复杂度：O(mn)
空间复杂度：O(1)
240.搜索二维矩阵
难度：⭐️⭐️
编写一个高效的算法来搜索 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
示例 2：
输入：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 = 20
输出：false
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= n, m <= 300
- -109 <= matrix[i][j] <= 9
- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
- -109 <= target <= 109
解法一 Z字形遍历
从右上或者左下开始遍历。从左上或右下看，矩阵正好是一个二叉搜索树。
Z字形遍历
解法二 按行二分查找
按行遍历矩阵，对每一行进行二分查找。
按行二分查找
public boolean searchMatrix(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
// 剪枝
if (target < matrix[i][0]) {
return false;
}
if (binarySearch(matrix[i], target)) {
return true;
}
}
return false;
}
private boolean binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
return true;
} else if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
289.生命游戏
难度：⭐️⭐️⭐️
根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
- 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
- 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
- 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
- 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是 同时 发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
给定当前 board 的状态，更新 board 到下一个状态。
注意 你不需要返回任何东西。
示例 1：
输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
示例 2：
输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]
提示：
- m == board.length
- n == board[i].length
- 1 <= m, n <= 25
- board[i][j] 为 0 或 1
解法一：拷贝矩阵
拷贝一个 m * n 的矩阵存放原始值，计算状态时根据原始值更新。
代码：略
解法二：增加状态
由于之前的细胞只有 0 和 1 两种状态，一轮遍历的过程中如果直接改值，会导致丢失原始状态，无法保证“同时”，因此额外引入 2 个状态，共 4 个状态： - -1，表示活细胞死亡，即 1 --> 0 - 0，死细胞状态不变 - 1，活细胞状态不变 - 2，死细胞复活，即 0 --> 1
遍历过程中，如果值是 -1 或 1，表示之前是活细胞，如果值是 0 或 2，表示之前是死细胞。
第二次再遍历，恢复成目标态。
增加状态标记
public void gameOfLife(int[][] board) {
int m = board.length;
int n = board[0].length;
// calculate
// -1(1 --> 0), 0, 1, 2 (0 --> 1)
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int v = board[i][j];
int liveCnt = 0;
for (int r = i - 1; r <= i + 1; r++) {
for (int c = j - 1; c <= j + 1; c++) {
if (r == i && c == j) {
continue;
}
if (0 <= r && r < m && 0 <= c && c < n) {
liveCnt += (Math.abs(board[r][c]) == 1 ? 1 : 0);
}
}
}
// rule 1
if (liveCnt < 2 && board[i][j] == 1) {
board[i][j] = -1;
}
// rule 3
if (liveCnt > 3 && board[i][j] == 1) {
board[i][j] = -1;
}
// rule 4
if (liveCnt == 3 && board[i][j] == 0) {
board[i][j] = 2;
}
}
}
// recover
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] < 1) {
board[i][j] = 0;
} else if (board[i][j] > 0) {
board[i][j] = 1;
}
}
}
}