CS Manual

Appearance

旋转 ​

48. 旋转图像 mid ​

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

画一个 _| 看看怎么翻转

java
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;
            }
        }
        // y=x 翻转
        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. 螺旋矩阵 mid ​

剑指 Offer 29. 顺时针打印矩阵 easy

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

控制好 4 个方向的边界

java
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        int u = 0, d = m - 1, l = 0, r = n - 1;
        while (true) {
            for (int i = l; i <= r; i++) res.add(matrix[u][i]);
            if (++u > d) break;
            for (int i = u; i <= d; i++) res.add(matrix[i][r]);
            if (--r < l) break;
            for (int i = r; i >= l; i--) res.add(matrix[d][i]);
            if (--d < u) break;
            for (int i = d; i >= u; i--) res.add(matrix[i][l]);
            if (++l > r) break;
        }
        return res;
    }
}

修改 ​

73. 矩阵置零 mid ​

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用 原地 算法。

解法 1: 2 个数组标记

二进制压缩

java
class Solution {
    public void setZeroes(int[][] matrix) {
        BitSet ir = new BitSet();
        BitSet ic = new BitSet();
        int r = matrix.length;
        int c = matrix[0].length;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (matrix[i][j] == 0) {
                    ir.set(i);
                    ic.set(j);
                }
            }
        }
        for (int i = 0; i < r; i++) {
            if (ir.get(i)) Arrays.fill(matrix[i], 0);
        }
        for (int j = 0; j < c; j++) {
            if (ic.get(j)) {
                for (int i = 0; i < r; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

解法 2: 2 个额外标记+数组自身标记

java
class Solution {
    public void setZeroes(int[][] m) {
        int r = m.length, c = m[0].length;
        boolean flagCol0 = false, flagRow0 = false;

        for (int i = 0; i < r; i++) {
            if (m[i][0] == 0) {
                flagCol0 = true;
                break;
            }
        }
        for (int j = 0; j < c; j++) {
            if (m[0][j] == 0) {
                flagRow0 = true;
                break;
            }
        }
        for (int i = 1; i < r; i++) {
            for (int j = 1; j < c; j++) {
                if (m[i][j] == 0) m[i][0] = m[0][j] = 0;
            }
        }
        for (int i = 1; i < r; i++) {
            for (int j = 1; j < c; j++) {
                if (m[i][0] == 0 || m[0][j] == 0) m[i][j] = 0;
            }
        }
        if (flagCol0) for (int i = 0; i < r; i++) m[i][0] = 0;
        if (flagRow0) for (int j = 0; j < c; j++) m[0][j] = 0;
    }
}

解法 3: 1 个额外标记+数组自身标记

用 m[0][0] 标记首行

java
class Solution {
    public void setZeroes(int[][] m) {
        int r = m.length, c = m[0].length;
        // 第0列含0标记
        boolean flagCol0 = false;
        for (int i = 0; i < r; i++) {
            if (m[i][0] == 0) flagCol0 = true;
            for (int j = 1; j < c; j++) { // 第0列本身就是标记
                if (m[i][j] == 0) m[i][0] = m[0][j] = 0;
            }
        }
        // 首行首列要最后更新
        for (int i = r - 1; i >= 0; i--) {
            for (int j = 1; j < c; j++) {
                if (m[i][0] == 0 || m[0][j] == 0) m[i][j] = 0;
            }
            if (flagCol0) m[i][0] = 0;
        }
    }
}

找值 ​

240. 搜索二维矩阵 II mid ​

剑指 Offer 04. 二维数组中的查找

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int r = matrix.length, c = matrix[0].length;
        int i = 0, j = c - 1;
        while (i < r && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] < target) i++;
            else j--;
        }
        return false;
    }
}

378. 有序矩阵中第 K 小的元素 mid ​

给你一个 n x n 矩阵 matrix, 其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

  • 你能否用一个恒定的内存(即 O(1) 内存复杂度)来解决这个问题?
  • 你能在 O(n) 的时间复杂度下解决这个问题吗?

求第 k 个元素有 3 种常用方法, 快排, 归并(堆排), 二分猜答案

解法 二分猜答案

找元素 e, 满足: 小于 e 的元素的数量 < k, 小于等于 e 的元素的数量 >= k
(小于等于 e 的元素数量 >= k) 的左边界
为什么收敛的边界值 mid 一定在矩阵中, 因为满足条件(小于等于 e 的元素数量 >= k)的左边界一定是矩阵中的值
cnt 可以按行计数, 从上往下越来越短

java
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int r = matrix.length, c = matrix[0].length;
        int l = matrix[0][0], h = matrix[r - 1][c - 1];
        while (l < h) {
            // 虚拟 1 个 mid
            int mid = l + (h - l >> 1);
            int cnt = cnt(matrix, mid);
            if (cnt < k)
                l = mid + 1;
            else
                h = mid;
        }
        return l;
    }

    // 统计<=mid 的元素数量
    private int cnt(int[][] matrix, int mid) {
        int i = 0;
        int j = matrix[0].length - 1;
        int res = 0;
        // 按行统计, 下一行比上一行短
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] <= mid) {
                res += j + 1;
                i++;
            } else j--;
        }
        return res;
    }
}

面积 ​

304. 二维区域和检索 - 矩阵不可变 mid ​

LCR 013. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1), 右下角 为 (row2, col2) 。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix)给定整数矩阵 matrix 进行初始化
  • sumRegion 返回 左上角 (row1, col1)、右下角(row2, col2) 所描述的子矩阵的元素 总和 。

解法 1 单行前缀和

记录每一行的前缀和

java
class NumMatrix {
    private int[][] arr;

    public NumMatrix(int[][] matrix) {
        int r = matrix.length, c = matrix[0].length;
        arr = new int[r][c + 1];
        for (int i = 0; i < r; i++) {
            for (int j = 1; j <= c; j++) {
                arr[i][j] = arr[i][j - 1] + matrix[i][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += arr[i][col2 + 1] - arr[i][col1];
        }
        return sum;
    }
}

解法 2 二维前缀和

记录矩阵的面积

java
class NumMatrix {
    private int[][] sum;

    public NumMatrix(int[][] matrix) {
        int r = matrix.length, c = matrix[0].length;
        sum = new int[r + 1][c + 1];
        for (int i = 0; i < r; i++) {
            int colSum = 0;
            for (int j = 0; j < c; j++) {
                colSum += matrix[i][j];
                // 上一行+colSum
                sum[i + 1][j + 1] = sum[i][j + 1] + colSum;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] + sum[row1][col1] - sum[row1][col2 + 1] - sum[row2 + 1][col1];
    }
}

重建 ​

566. 重塑矩阵 easy ​

在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。

给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。

如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

根据 m,n 求出第 idx 个

java
class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int m = nums.length, n = nums[0].length;
        if (m * n != r * c) return nums;

        int[][] reshapedMatrix = new int[r][c];
        for (int i = 0; i < r * c; i++) {
            reshapedMatrix[i / c][i % c] = nums[i / n][i % n];
        }
        return reshapedMatrix;
    }
}

特殊矩阵 ​

766. 托普利茨矩阵 easy ​

给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。

如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。

java
class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] != matrix[i - 1][j - 1]) {
                    return false;
                }
            }
        }
        return true;
    }
}