矩阵类问题处理技巧

矩阵类问题处理技巧

作者:Grey

原文地址:

博客园:矩阵类问题处理技巧

CSDN:矩阵类问题处理技巧

给定一个正方形矩阵,原地调整成顺时针90度转动的样子

题目链接见:LeetCode 48. Rotate Image

本题主要的限制条件是:原地调整,即不开辟额外的二维数组来做。

主要思路如下

第一步,先处理外围的圈 然后同理依次处理每个内圈。

矩阵类问题处理技巧插图

第二步,每个圈分组,组内每次一个元素占据下一个元素的位置,如果是N*N就分(N-1)*(N-1)个组。如下图。颜色一样的就是同一组。

矩阵类问题处理技巧插图1

第三步,每个组的每个数可以通过组号来定位。如下图:

矩阵类问题处理技巧插图1

编号一样的就是同一组,同一组的某个位置,按顺时针方向,可以很方便定位到本组下一个位置。

组内调整的核心代码如下

    private static void rotate(int n, int[][] matrix, int zuoshangX, int zuoshangY, int youxiaX, int youxiaY) {
        int zu = n - 1;
        int youshangX = zuoshangX;
        int youshangY = youxiaY;
        int zuoxiaX = youxiaX;
        int zuoxiaY = zuoshangY;
        for (int i = 1; i 

完整代码见

class Solution {
    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        int zuoshangX = 0;
        int zuoshangY = 0;
        int youxiaX = n - 1;
        int youxiaY = n - 1;
        while (n > 0) {
            // 先处理外围,然后逐步处理内圈。
            rotate(n, matrix, zuoshangX++, zuoshangY++, youxiaX--, youxiaY--);
            n -= 2;
        }
    }

    private static void rotate(int n, int[][] matrix, int zuoshangX, int zuoshangY, int youxiaX, int youxiaY) {
        int zu = n - 1;
        int youshangX = zuoshangX;
        int youshangY = youxiaY;
        int zuoxiaX = youxiaX;
        int zuoxiaY = zuoshangY;
        for (int i = 1; i 

给定一个长方形矩阵,实现转圈打印

LeetCode 54. Spiral Matrix

和上一题类似,先打印外围圈圈,然后切换到内圈,用同样的方式打印内圈,依次循环。

打印的时候,我们只需要定位左上和右下两个点的坐标位置即可确定一个矩形。

矩阵类问题处理技巧插图2

需要注意的是,最后有可能是一条直线,比如下述两种情况中的标红位置

矩阵类问题处理技巧插图3

矩阵类问题处理技巧插图4

对于形成一条直线的情况,单独处理并打印即可。

完整代码见

class Solution {
    public static List spiralOrder(int[][] matrix) {
        if (null == matrix || matrix.length == 0 || matrix[0].length == 0) {
            return new ArrayList();
        }
        int m = matrix.length;
        int n = matrix[0].length;
        // 左上角点
        int a = 0, b = 0;
        // 右下角点
        int c = m - 1, d = n - 1;
        List ans = new ArrayList();
        while (a  ans) {
        if (a == c) {
            // 形成一条直线:共行
            for (int i = b; i  b; i--) {
            ans.add(matrix[c][i]);
        }
        for (int i = c; i > a; i--) {
            ans.add(matrix[i][b]);
        }
    }
}

zigzag打印矩阵

题目描述见:LintCode 185 · Matrix Zigzag Traversal

zigzag 方式如下

矩阵类问题处理技巧插图5

本题的主要思路是

从左上角的开始位置,准备两个变量 A 和 B,A 往左边走,走到不能再走的时候,往下走
B 往下走,走到不能再往下的时候,往左边走,每次 AB 构成的连线进行打印(方向交替变化)

完整代码见:

public class Solution {
    /**
     * @param matrix: An array of integers
     * @return: An array of integers
     */
    public static int[] printZMatrix(int[][] matrix) {
        if (null == matrix || matrix.length == 0 || matrix[0].length == 0) {
            return null;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[] ans = new int[m * n];
        ans[0] = matrix[0][0];
        // 右边-->下边
        int a = 0, b = 0;
        // 下边-->右边
        int c = 0, d = 0;
        int index = 1;
        boolean topToDown = true;
        for (int k = 0; k = a; i--) {
                    ans[index++] = matrix[i][j++];
                }
            }
            topToDown = !topToDown;
        }
        return ans;
    }
}

螺旋打印星号

依旧是先处理外圈,然后依次内圈的处理方式,

完整代码见

package snippet;

// 螺旋打印星号
public class Code_0093_PrintStar {

    public static void printStar(int N) {
        int leftUp = 0;
        int rightDown = N - 1;
        char[][] m = new char[N][N];
        for (int i = 0; i  leftUp; col--) {
            m[rightDown][col] = '*';
        }
        for (int row = rightDown - 1; row > leftUp + 1; row--) {
            m[row][leftUp + 1] = '*';
        }
    }

    public static void main(String[] args) {
        printStar(5);
    }

}

打印结果如下

* * * * * 
        * 
  * *   * 
  *     * 
  * * * * 

更多

算法和数据结构笔记

文章来源于互联网:矩阵类问题处理技巧

THE END
分享
二维码