力扣hot100--2

力扣hot100-矩阵

题目：矩阵置零

原题链接：矩阵置零

题解

方法：通过先标记需要置为 0 的位置，再进行修改，避免了在遍历矩阵时直接更改元素，避免了覆盖掉尚未检查的元素。（先标记再置零）

row[i] || col[j] 的意思就是：如果 第 i 行 或 第 j 列 中有任何一个被标记为需要置为 0，那么当前元素 matrix[i][j] 就应该被置为 0。

    public void setZeroes(int[][] matrix) {
        boolean[] row = new boolean[matrix.length];
        boolean[] col = new boolean[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

下面这个逻辑更清晰：

    public void setZeroes(int[][] matrix) {
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    // 行变为0
                    rowToZero(matrix, i, visited);
                    // 列变为0
                    cloToZero(matrix, j, visited);
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (visited[i][j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    private void rowToZero(int[][] matrix, int i, boolean[][] visited) {
        for (int j = 0; j < matrix[i].length; j++) {
            visited[i][j] = true;
        }
    }

    private void cloToZero(int[][] matrix, int j, boolean[][] visited) {
        for (int i = 0; i < matrix.length; i++) {
            visited[i][j] = true;
        }
    }

题目：螺旋矩阵

原题链接：螺旋矩阵

题解

思路解析：

1. 定义边界：我们需要通过 4 个变量来维护矩阵的边界：

   • top：表示当前螺旋矩阵的上边界，初始化为 0。
   • bottom：表示当前螺旋矩阵的下边界，初始化为矩阵的最后一行索引。
   • left：表示当前螺旋矩阵的左边界，初始化为 0。
   • right：表示当前螺旋矩阵的右边界，初始化为矩阵的最后一列索引。

2. 顺时针遍历：按照螺旋顺序进行遍历：

   • 从左到右：遍历 top 边界上的一行元素，然后 top++（即上边界下移）。
   • 从上到下：遍历 right 边界上的一列元素，然后 right--（即右边界左移）。
   • 从右到左：遍历 bottom 边界上的一行元素，然后 bottom--（即下边界上移）。
   • 从下到上：遍历 left 边界上的一列元素，然后 left++（即左边界右移）。

3. 结束条件：遍历结束的条件是 top > bottom 或 left > right，即上下边界或左右边界错位。

每遍历一行或者一列，记得收缩相应的空间。（已经遍历的就不在遍历了）

public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int top = 0;
        int right = matrix[0].length - 1;
        int bottom = matrix.length - 1;
        int left = 0;

        while (left <= right && top <= bottom) {
            // 左到右
            // 边界是left right，i在范围里面移动。 保持行不变
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            top++;
            // 上到下
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--;
            // 右到左
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    res.add(matrix[bottom][i]);
                }
                bottom--;
            }
            // 下到上
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    res.add(matrix[i][left]);
                }
                left++;
            }
        }
        return res;
    }

题目：旋转图像

原题链接：旋转图像

题解

矩阵转置：将矩阵的行列互换得到的新矩阵称为转置矩阵。

1 2 3           1 4 7             7 4 1
4 5 6 ==转置==》 2 5 8 ==行反转==>  8 5 2
7 8 9           3 6 9             9 6 3

 public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // 1. 对角线翻转 矩阵转置
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        
        // 2. 每一行反转
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }