数据结构基础之《（19）—矩阵处理》

一、zigzag打印矩阵

Z字形打印矩阵
 1  2  3  4  5  6
 7  8  9  10 11 12
 13 14 15 16 17 18
打印顺序：1,2,7,13,8,3,4,9,14...

核心技巧：找到coding上的宏观调度

左上角有A、B两个点，A往右一步一步走，B往下一步一步走
写一个函数从左下往右上打印，调度问题交给点A和B来移动

package class09;/*** Z字形打印矩阵*/
public class Code06_ZigZagPrintMatrix {public static void printMatrixZigZag(int[][] matrix) {int aR = 0; //A的行号int aC = 0; //A的列号int bR = 0; //B的行号int bC = 0; //B的列号int endR = matrix.length - 1; //最后的行号int endC = matrix[0].length - 1; //最后的列号boolean fromUp = false; //是不是从右上往左下打印while (aR != endR + 1) { //A的行号，不等于最后的行号+1，A到了终点printLevel(matrix, aR, aC, bR, bC, fromUp);aR = (aC == endC ? aR + 1 : aR); //A的列数到最后一列，A的行号才加1aC = (aC == endC ? aC : aC + 1); //A的列数到最后一列，A的列数不变，否则A的列数加1bC = (bR == endR ? bC + 1 : bC); //B的行数到最后一行，B的列数加1，否则B的列数不变bR = (bR == endR ? bR : bR + 1); //B的行数到最后一行，B的行数不变，否则B的行数加1fromUp = !fromUp; //打印方向}System.out.println();}/*** 告诉你斜线的两端是A和B，方向也告诉你，就可以打印了* @param m* @param tR* @param tC* @param dR* @param dC* @param f*/public static void printLevel(int[][] m, int tR, int tC, int dR, int dC, boolean f) {if (f) {while (tR != dR + 1) { //右上往左下打印System.out.print(m[tR++][tC--] + " ");}} else {while (dR != tR - 1) { //左下往右上打印System.out.print(m[dR--][dC++] + " ");}}}public static void main(String[] args) {int[][] matrix = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};printMatrixZigZag(matrix);}
}

打印结果：

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16 

二、转圈打印矩阵

按照层考虑：

第一层的结束的位置和第二层开始的位置挨着，第二层结束的位置和第三层开始的位置挨着。。。

思路：
获取四个角的点，打印时判断位置是否到四个角

package class09;/*** 回形打印矩阵*/
public class Code05_PrintMatrixSpiralOrder {public static void sprialOrderPrint(int[][] matrix) {int tR = 0;int tC = 0;int dR = matrix.length - 1;int dC = matrix[0].length - 1;while (tR <= dR && tC <= dC) {printEdge(matrix, tR++, tC++, dR--, dC--); //左上角点往右下方移动，右下角点往左上方移动}}/*** * @param m* @param tR 左上角点的行号* @param tC 左上角点的列号* @param dR 右下角点的行号* @param dC 右下角点的列号*/public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) {if (tR == dR) { //是一条横线时for (int i = tC; i <= dC; i++) {System.out.print(m[tR][i] + " ");}} else if (tC == dC) { //是一条竖线时for (int i = tR; i <= dR; i++) {System.out.print(m[i][tC] + " ");}} else {int curC = tC;int curR = tR;while (curC != dC) {System.out.print(m[tR][curC] + " ");curC++;}while (curR != dR) {System.out.print(m[curR][dC] + " ");curR++;}while (curC != tC) {System.out.print(m[dR][curC] + " ");curC--;}while (curR != tR) {System.out.print(m[curR][tC] + " ");curR--;}}}public static void main(String[] args) {int[][] matrix = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};sprialOrderPrint(matrix);}
}

打印结果：

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 

三、原地旋转正方形矩阵

package class09;/*** 原地旋转正方形矩阵*/
public class Code04_RotateMatrix {public static void rotate(int[][] matrix) {int a = 0;int b = 0;int c = matrix.length - 1;int d = matrix[0].length - 1;while (a < c) { //只要关注行不越界rotateEdge(matrix, a++, b++, c--, d--);}}/*** 一个圈里面怎么转* @param m* @param a* @param b* @param c* @param d*/public static void rotateEdge(int[][] m, int a, int b, int c, int d) {int tmp = 0;for (int i = 0; i < d - b; i++) {tmp = m[a][b + i];m[a][b + i] = m[c - i][b];m[c - i][b] = m[c][d - i];m[c][d - i] = m[a + i][d];m[a + i][d] = tmp;}}public static void printMatrix(int[][] matrix) {for (int i = 0; i != matrix.length; i++) {for (int j = 0; j != matrix[0].length; j++) {System.out.print(matrix[i][j] + " ");}System.out.println();}}public static void main(String[] args) {int[][] matrix = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};printMatrix(matrix);System.out.println("====================");rotate(matrix);printMatrix(matrix);}
}

打印结果：

1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16 
====================
13 9 5 1 
14 10 6 2 
15 11 7 3 
16 12 8 4