矩阵类问题处理技巧

矩阵类问题处理技巧

作者：Grey

原文地址：

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

CSDN：矩阵类问题处理技巧

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

题目链接见：LeetCode 48. Rotate Image

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

主要思路如下

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

第二步，每个圈分组，组内每次一个元素占据下一个元素的位置，如果是N*N就分（N-1）*（N-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 <= zu; i++) {             // 每组内部调整             int tmp = matrix[zuoshangX][zuoshangY];             matrix[zuoshangX][zuoshangY++] = matrix[zuoxiaX][zuoxiaY];             matrix[zuoxiaX--][zuoxiaY] = matrix[youxiaX][youxiaY];             matrix[youxiaX][youxiaY--] = matrix[youshangX][youshangY];             matrix[youshangX++][youshangY] = tmp;         }     } 

完整代码见

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 <= zu; i++) {             // 每组内部调整             int tmp = matrix[zuoshangX][zuoshangY];             matrix[zuoshangX][zuoshangY++] = matrix[zuoxiaX][zuoxiaY];             matrix[zuoxiaX--][zuoxiaY] = matrix[youxiaX][youxiaY];             matrix[youxiaX][youxiaY--] = matrix[youshangX][youshangY];             matrix[youshangX++][youshangY] = tmp;         }     } }  

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

LeetCode 54. Spiral Matrix

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

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

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

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

完整代码见

class Solution {     public static List<Integer> 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<Integer> ans = new ArrayList<>();         while (a <= c && b <= d) {             spiral(matrix, a++, b++, c--, d--, ans);         }         return ans;     }      public static void spiral(int[][] matrix, int a, int b, int c, int d, List<Integer> ans) {         if (a == c) {             // 形成一条直线：共行             for (int i = b; i <= d; i++) {                 ans.add(matrix[a][i]);             }             return;         }         if (b == d) {             // 形成一条直线：共列             for (int i = a; i <= c; i++) {                 ans.add(matrix[i][b]);             }             return;         }         for (int i = b; i < d; i++) {             ans.add(matrix[a][i]);         }         for (int i = a; i < c; i++) {             ans.add(matrix[i][d]);         }         for (int i = d; 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 方式如下

本题的主要思路是

从左上角的开始位置，准备两个变量 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 < m + n; k++) {             if (b < n - 1) {                 b++;             } else if (b == n - 1) {                 a++;             }             if (c < m - 1) {                 c++;             } else if (c == m - 1) {                 d++;             }             if (topToDown) {                 int j = b;                 for (int i = a; i <= c; i++) {                     ans[index++] = matrix[i][j--];                 }             } else {                 int j = d;                 for (int i = c; i >= 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 < N; i++) {             for (int j = 0; j < N; j++) {                 m[i][j] = ' ';             }         }         while (leftUp <= rightDown) {             set(m, leftUp, rightDown);             leftUp += 2;             rightDown -= 2;         }         for (int i = 0; i < N; i++) {             for (int j = 0; j < N; j++) {                 System.out.print(m[i][j] + " ");             }             System.out.println();         }     }      public static void set(char[][] m, int leftUp, int rightDown) {         for (int col = leftUp; col <= rightDown; col++) {             m[leftUp][col] = '*';         }         for (int row = leftUp + 1; row <= rightDown; row++) {             m[row][rightDown] = '*';         }         for (int col = rightDown - 1; col > 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);     }  }  

打印结果如下

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

更多

算法和数据结构笔记