面试经典 150 题-矩阵

LeetCode 面试经典 150 题-矩阵

有效数独

模拟

先判断行，再判断列，再判断九宫格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] cnt = new int[10];
        // 判断行
        for (int i = 0; i < 9; i++) {
            Arrays.fill(cnt, 0);  // 每次遍历新的一行时，重置计数器
            for (int j = 0; j < 9; j++) {
                if (Character.isDigit(board[i][j])) {
                    int num = board[i][j] - '0';
                    if (cnt[num] > 0) {
                        return false;
                    }
                    cnt[num]++;
                }
            }
        }
        // 判断列
        for (int j = 0; j < 9; j++) {
            Arrays.fill(cnt, 0);  // 每次遍历新的一列时，重置计数器
            for (int i = 0; i < 9; i++) {
                if (Character.isDigit(board[i][j])) {
                    int num = board[i][j] - '0';
                    if (cnt[num] > 0) {
                        return false;
                    }
                    cnt[num]++;
                }
            }
        }
        // 判断九宫格
        for (int blockRow = 0; blockRow < 3; blockRow++) {
            for (int blockCol = 0; blockCol < 3; blockCol++) {
                Arrays.fill(cnt, 0);  // 每次遍历新的一宫格时，重置计数器
                for (int i = blockRow * 3; i < blockRow * 3 + 3; i++) {
                    for (int j = blockCol * 3; j < blockCol * 3 + 3; j++) {
                        if (Character.isDigit(board[i][j])) {  // 如果是数字
                            int num = board[i][j] - '0';
                            if (cnt[num] > 0) {  // 如果该数字已经出现过
                                return false;
                            }
                            cnt[num]++;
                        }
                    }
                }
            }
        }

        return true;
    }
}
JAVA
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

一次遍历

创建二维数组 rows 和 columns 分别记录数独的每一行和每一列中的每个数字的出现次数，创建三维数组 subboxes 记录数独的每一个小九宫格中的每个数字的出现次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] cols = new int[9][9];
        int[][][] subboxes = new int [3][3][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // 如果是数字
                if (board[i][j] != '.') {
                    int index = board[i][j] - '0' - 1;
                    // 更新
                    rows[i][index]++;
                    cols[j][index]++;
                    subboxes[i/3][j/3][index]++;
                    // 不合法直接退出
                    if (rows[i][index] > 1 || cols[j][index] > 1 || subboxes[i/3][j/3][index] > 1) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}
JAVA
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

螺旋矩阵

模拟

定义四个方向的边界：

  • 初始：left = 0, right = n-1, top = 0, down = m - 1；
  • 循环遍历：初始时向右走，到达右边界后，更新上边界，继续向下，到达下边界后，更新右边界，继续向左，到达左边界后，更新下边界，继续向上，到达上边界后，更新左边界，继续向右。
  • 结束条件判断：top > down || left > right。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = n - 1, up = 0, down = m - 1;

        List<Integer> res = new ArrayList<>();
        while (true) {
            // 向右走
            for (int i = left; i <= right; i++) {
                res.add(matrix[up][i]);
            }
            // 更新上边界并判断是否越界
            up += 1;
            if (up > down) {
                break;
            }
            // 向下走
            for (int i = up; i <= down; i++) {
                res.add(matrix[i][right]);
            }
            // 更新右边界并判断是否越界
            right -= 1;
            if (right < left) {
                break;
            }
            // 向左走
            for (int i = right; i >= left; i--) {
                res.add(matrix[down][i]);
            }
            // 更新下边界并判断是否越界
            down -= 1;
            if (down < up) {
                break;
            }
            // 向上走
            for (int i = down; i >= up; i--) {
                res.add(matrix[i][left]);
            }
            // 更新左边界并判断是否越界
            left += 1;
            if (left > right) {
                break;
            }
        }

        return res;
    }
}
JAVA
  • 时间复杂度：$O(mn)$
  • 空间复杂度：O(1)，返回值不计入。

旋转图像

数学

  • (i, j) -> (j, n-i-1)
  • (j, n-i-1) -> (n-i-1, n-j-1)
  • (n-i-1, n-j-1) -> (n-j-1, i)
  • (n-j-1, i) -> (i, j)

只需要遍历四分之一的窗格就能完成所有的旋转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < (n + 1) / 2; i++) {
            for (int j = 0; j < n / 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;
            }
        }
    }
}
JAVA
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(1)

水平翻转+主对角线翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
            }
        } 
    }
}
JAVA
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(1)

矩阵置零

模拟

  1. 额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。
  2. 预处理出两个标记变量
  3. 使用其他行与列去处理第一行与第一列.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean row0 = false, col0 = false;

        // 初始化标记变量
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                col0 = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                row0 = true;
                break;
            }
        }

        // 初始化第一行和第一列
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    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] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 置零第一行和第一列
        if (row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}
JAVA
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(1)

生命游戏

分析

  1. 规则 1：如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡。这时候，将细胞值改为 -1，代表这个细胞过去是活的现在死了；
  2. 规则 2：如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活。这时候不改变细胞的值，仍为 1；
  3. 规则 3：如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡。这时候，将细胞的值改为 -1，代表这个细胞过去是活的现在死了。可以看到，因为规则 1 和规则 3 下细胞的起始终止状态是一致的，因此它们的复合状态也一致；
  4. 规则 4：如果死细胞周围正好有三个活细胞，则该位置死细胞复活。这时候，将细胞的值改为 2，代表这个细胞过去是死的现在活了。

对于最终的输出，需要将 board 转成 0，1 的形式。因此这时候需要再遍历一次数组，将复合状态为 2 的细胞的值改为 1，复合状态为 -1 的细胞的值改为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public void gameOfLife(int[][] board) {
        int[] neighbors = {0, 1, -1};
        int m = board.length;
        int n = board[0].length;

        // 遍历
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                // 统计活细胞数
                int cnt = 0;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            // 相邻位置坐标
                            int r = row + neighbors[i];
                            int c = col + neighbors[j];
                            // 查看相邻的细胞是否是活细胞
                            if ((r < m && r >= 0) && (c < n && c >= 0) && (Math.abs(board[r][c]) == 1)) {
                                cnt++;
                            }
                        }
                    }
                }

                // 规则1,3
                if ((board[row][col] == 1) && (cnt < 2 || cnt > 3)) {
                    board[row][col] = -1;
                }

                // 规则4
                if (board[row][col] == 0 && cnt == 3) {
                    board[row][col] = 2;
                }
            }
        }

        // 更新状态
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] > 0) {
                    board[i][j] = 1;
                } else {
                    board[i][j] = 0;
                }
            }
        }
    }
}
JAVA
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(1)
算法笔记 > 矩阵
#矩阵
面试经典 150 题-矩阵
http://example.com/2025/01/04/posts/hot150-4/
作者
Xuan Yang
发布于
2025年1月4日
许可协议