数据结构基础之19矩阵处理
目录
数据结构基础之《（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的行号才加1
aC = (aC == endC ? aC : aC + 1); //A的列数到最后一列，A的列数不变，否则A的列数加1
bC = (bR == endR ? bC + 1 : bC); //B的行数到最后一行，B的列数加1，否则B的列数不变
bR = (bR == endR ? bR : bR + 1); //B的行数到最后一行，B的行数不变，否则B的行数加1
fromUp = !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