当前位置：首页 > article >正文

java算法学习索引之数组矩阵问题

article 2024/12/23 18:43:18

一将正方形矩阵顺时针转动90°

给定一个N×N的矩阵matrix，把这个矩阵调整成顺时针转动90°后的形式。

顺时针转动90°后为：

【要求】额外空间复杂度为O（1）。

public void rotate(int[][] matrix) {
    int tR = 0; // 左上角行坐标
    int tC = 0; // 左上角列坐标
    int dR = matrix.length - 1; // 右下角行坐标
    int dC = matrix[0].length - 1; // 右下角列坐标
    while (tR < dR) { // 循环条件：左上角坐标不能超过右下角坐标
        rotateEdge(matrix, tR++, tC++, dR--, dC--); // 旋转每一层
    }
}

private void rotateEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
    int times = dC - tC; // 当前层的元素个数
    int tmp = 0; // 用于交换的中间变量
    for (int i = 0; i < times; i++) { // 循环遍历当前层的元素
        tmp = matrix[dR][tC + i];
        matrix[tR][tC + i] = matrix[dR - i][tC];
        matrix[dR - i][tC] = matrix[dR][dC - i];
        matrix[dR][dC - i] = matrix[tR + i][dC];
        matrix[tR + i][dC] = tmp;
    }
}

这段代码实现了一个将二维数组（矩阵）顺时针旋转90度的方法，采用边界逐层旋转的方式。

rotate() 方法中，使用四个变量来记录矩阵的左上角坐标和右下角坐标，并在 while 循环中不断收缩边界，对每一层使用 rotateEdge() 方法来旋转。

rotateEdge() 方法是旋转操作的核心，其中 times 记录当前层的元素个数，tmp 用于保存当前要旋转的元素，通过四个 for 循环分别完成旋转操作，具体如下：

将矩阵的右上角元素 m[dR][tC+i] 赋值给左上角元素 m[tR][tC+i]
将矩阵的左下角元素 m[dR-i][tC] 赋值给右上角元素 m[tR][tC+i]
将矩阵的左上角元素 m[dR][tC-i] 赋值给左下角元素 m[dR-i][tC]
将 tmp 值赋值给右下角元素 m[tR+i][dC]

在 rotateEdge() 方法中，使用 for 循环遍历每一层元素，i 从 0 开始，每次循环收缩一圈，直到完成该层所有元素的旋转。

二 “之”字形打印矩阵

【题目】给定一个矩阵matrix，按照“之”字形的方式打印这个矩阵，例如：

“之”字形打印的结果为：1，2，5，9，6，3，4，7，10，11，8，12。

【要求】额外空间复杂度为O（1）。

要按照"之"字形的方式打印矩阵，我们可以根据打印方向分为两种情况：从左上到右下以及从右下到左上。我们可以使用两个变量来表示当前打印的行和列，根据当前行和列的奇偶性来确定打印顺序。

下面是按照"之"字形打印矩阵的 Java 代码实现：

public void printZMatrix(int[][] matrix) {
    if (matrix == null || matrix.length == 0) {
        return;
    }
    int row = matrix.length; // 矩阵行数
    int col = matrix[0].length; // 矩阵列数
    int tR = 0; // 左上角行坐标
    int tC = 0; // 左上角列坐标
    int dR = 0; // 右下角行坐标
    int dC = 0; // 右下角列坐标
    boolean fromUp = false; // 打印方向标志位，false 表示从右下到左上，true 表示从左上到右下

    while (tR < row) {
        printLevel(matrix, tR, tC, dR, dC, fromUp);

        // 更新左上角和右下角的坐标
        tR = tC == col - 1 ? tR + 1 : tR; // 如果当前列已经到达最后一列，则向下移动
        tC = tC == col - 1 ? tC : tC + 1; // 如果当前列已经到达最后一列，则不再向右移动
        dC = dR == row - 1 ? dC + 1 : dC; // 如果当前行已经到达最后一行，则向右移动
        dR = dR == row - 1 ? dR : dR + 1; // 如果当前行已经到达最后一行，则不再向下移动
        fromUp = !fromUp; // 改变打印方向
    }
}

private void printLevel(int[][] matrix, int tR, int tC, int dR, int dC, boolean fromUp) {
    if (fromUp) { // 从左上到右下打印
        while (tR <= dR && tC >= dC) {
            System.out.print(matrix[tR++][tC--] + " ");
        }
    } else { // 从右下到左上打印
        while (dR >= tR && dC <= tC) {
            System.out.print(matrix[dR--][dC++] + " ");
        }
    }
}

以上代码中，printZMatrix() 方法用于控制行和列的遍历，根据打印的方向调用 printLevel() 方法来打印每一层的元素。

printLevel() 方法根据打印方向，使用 while 循环来打印每一层的元素，从左上到右下打印时，行坐标递增，列坐标递减；从右下到左上打印时，行坐标递减，列坐标递增。

希望以上代码能够帮助到你！如果你还有其他问题，请随时向我提问。

查看全文

http://www.kler.cn/a/137123.html