大家好，欢迎来到IT知识分享网。
矩阵宏观调度：Zigzag扫描打印矩阵matrix，图像工程的一种编码
提示：极其重要的矩阵处理技巧，矩阵下标的宏观调度
题目
给你一个矩阵，请你用Zigzag扫描打印矩阵matrix
一、审题
示例：
matrix=
1 2 3 4
5 6 7 8
9 10 11 12
打印顺序是这样的
1 2 5 9 6 3 4 7 10 11 8 12
由于空间逻辑上扫描打印的轨迹酷似Z形状，故叫zigzag扫描打印。
zigzag扫描打印矩阵的宏观调度
记住这种宏观调度策略，矩阵N行M列
（1）令AB最开始都在0 0原点【Ar=Br=0 && Ac=Bc=0】
r是row代表行下标，c是column代表列下标
宏观思想就是AB同步走，A先往右，同时B往下走
A到右边界M，转头往下走
B到下边界N，转头往右走
等啥时候AB再相遇【Ar=Br=N-1 && Ac=Bc=M-1】，结束扫描
上图中，
最开始A的列Ac，Ac还没有到右边界M-1，则可以先往右增加，此时Ar不能变动，
如果Ac=M-1，到右边界了，Ar才可以开始增加，A往下走，所以Ar的判断条件和走法是图中第三行的情况。
类似的，
最开始B的行Br，Br还没有到下边界N-1，则可以先往下增加，此时Bc不能变动，
如果Br=N-1，到下边界了，Bc才可以开始增加，B往右走，所以Bc的判断条件和走法时图中的第四行的情况。
看明白了这个宏观调度了吧！
实际操作的时候要小心！！！
实际操作的时候要小心！！！
实际操作的时候要小心！！！
由于Ac变化在前，Ac会影响Ar，所以把Ar的更新放在前面，否则容易导致Ar提前变大。
同样由于Br的变化在前，Br会影响Bc的更新，所以把Bc的更新放在前面，否则容易导致Bc提前变大
Ar = Ac == M - 1 ? Ar + 1: Ar;//这句得放前面
Ac = Ac == M - 1 ? Ac : Ac + 1;//Ac到右边界不能动
Bc = Br == N - 1 ? Bc + 1: Bc;//这句话得放前面！！！
Br = Br == N - 1 ? Br : Br + 1;//到下边界就停
你不信把代码调换试试，
Ac = Ac == M - 1 ? Ac : Ac + 1;//Ac到右边界不能动
Ar = Ac == M - 1 ? Ar + 1: Ar;//这句得放前面
Br = Br == N - 1 ? Br : Br + 1;//到下边界就停
Bc = Br == N - 1 ? Bc + 1: Bc;//这句话得放前面！！！
中途，由于Ac抵达M-1，Ar里面就得到了Ac == M – 1满足的条件，就会触发Ar=Ar + 1，
相当于Ac和Ar同时+1，你就不是A水平走了，而是斜着走，这是错的
我们要求A水平走，再垂直走，要求B先垂直走，再水平走
AB的横纵坐标绝对不能同时变，否则就是斜着走！！！
（2）上面（1）宏观调度的每一步，每一个AB点的连线，都要连续打印很多数，直接定义一个函数打印
abPrint(Ar,Ac,Br,Bc,fromAB)
要么是从A–B打印，要么是从B–A打印，2种状态，就用Boolean值标记吧
不妨设A–B打印的标志fromAB=true。
显然，一开始是从B–A，所以取fromAB=false
行，咱们先手撕打印函数的代码，给定AB坐标，和fromAB的标记，咱们顺溜打印一条线
如果是从A–B打印，那顺溜的就是Ac–，Ar++，这样从A点挪到B点打印完事之后就停止
如果是从B–A打印，那顺溜的就是Bc++，Br–，这样从B点挪到A点打印完事之后就停止
打印的代码如下：
//复习zigzag扫描打印
//从A--B，或者B--A一条线顺溜的打印
public static void abPrint(int[][] arr, int Ar, int Ac, int Br, int Bc, boolean fromAB){
//一进来如果A=B点，打印一个即可
if (Ar == Br && Ac == Bc) System.out.print(arr[Ar][Ac] +" ");
//从A--B一条线顺溜的打印
while (fromAB && Ar != Br){
//只要A还没有与B相遇则打印一溜
System.out.print(arr[Ar][Ac] +" ");
Ar++;
Ac--;//从右上角A往左下角B滑动
}
//从B--A一条线顺溜的打印
while (!fromAB && Br != Ar){
//只要B还没有与A相遇则打印一溜
System.out.print(arr[Br][Bc] +" ");
Br--;
Bc++;//从左下角B往右上角A滑动
}
}
手撕zigzag扫描打印矩阵的代码
上面说的Ar的更新放在前面，Bc的更新一定放前面，要记住了
你不信自己调试代码看，是错的，斜着走，打印就会少了很多数据
咱们手撕zigzag扫描打印矩阵的代码如下：
//zigzag扫描打印矩阵的宏观调度
public static void zigzagPrintMatrixReview(int[][] arr){
if (arr == null || arr.length == 0) return;
int N = arr.length;
int M = arr[0].length;//边界
//（1）令AB最开始都在0 0原点【Ar=Br=0 && Ac=Bc=0】
//宏观思想就是AB同步走，A先往右，同时B往下走
//A到右边界M，转头往下走
//B到下边界N，转头往右走
//等啥时候AB再相遇【Ar=Br=N-1 && Ac=Bc=M-1】，结束扫描
int Ar = 0;
int Br = 0;
int Ac = 0;
int Bc = 0;
boolean fromAB = false;//开始是B--A一溜打印
while (Ar < N){
//（2）上面（1）宏观调度的每一步，每一个AB点的连线，都要连续打印很多数
abPrint(arr, Ar, Ac, Br, Bc, fromAB);
//打印完A--B，或者B--A就要调度AB同步走
//最开始A的列Ac，Ac还没有到右边界M-1，则可以先往右增加，此时Ar不能变动，
//如果Ac=M-1，到右边界了，Ar才可以开始增加，A往下走，所以Ar的判断条件和走法是图中第三行的情况。
Ar = Ac == M - 1 ? Ar + 1: Ar;//这句得放前面
Ac = Ac == M - 1 ? Ac : Ac + 1;//Ac到右边界不能动
//类似的，
//最开始B的行Br，Br还没有到下边界N-1，则可以先往下增加，此时Bc不能变动，
//如果Br=N-1，到下边界了，Bc才可以开始增加，B往右走，所以Bc的判断条件和走法时图中的第四行的情况。
Bc = Br == N - 1 ? Bc + 1: Bc;//这句话得放前面！！！
Br = Br == N - 1 ? Br : Br + 1;//到下边界就停
//掉头扫描
fromAB = !fromAB;
}
//当AB相遇，下一次Ar就会越界的
}
public static void test(){
int[][] arr = {
{
1, 2, 3, 4, 5},
{
6, 7, 8, 9, 10},
{
11, 12, 13, 14,15}
};//打印1,2,6,11,7,3,4,8,12,13，9,5,10,14,15
zigzagPrintMatrix(arr);
System.out.println();
zigzagPrintMatrixReview(arr);
}
public static void main(String[] args) {
test();
}
结果如下：
1 2 6 11 7 3 4 8 12 13 9 5 10 14 15
1 2 6 11 7 3 4 8 12 13 9 5 10 14 15
错误的Ar和Bc的更新顺序
把代码调换试试，
Ac = Ac == M - 1 ? Ac : Ac + 1;//Ac到右边界不能动
Ar = Ac == M - 1 ? Ar + 1: Ar;//这句得放前面
Br = Br == N - 1 ? Br : Br + 1;//到下边界就停
Bc = Br == N - 1 ? Bc + 1: Bc;//这句话得放前面！！！
整体如下：
//错误的zigzag扫描打印矩阵的宏观调度
public static void wrongZigzagPrintMatrixReview(int[][] arr){
if (arr == null || arr.length == 0) return;
int N = arr.length;
int M = arr[0].length;//边界
//（1）令AB最开始都在0 0原点【Ar=Br=0 && Ac=Bc=0】
//宏观思想就是AB同步走，A先往右，同时B往下走
//A到右边界M，转头往下走
//B到下边界N，转头往右走
//等啥时候AB再相遇【Ar=Br=N-1 && Ac=Bc=M-1】，结束扫描
int Ar = 0;
int Br = 0;
int Ac = 0;
int Bc = 0;
boolean fromAB = false;//开始是B--A一溜打印
while (Ar < N){
//（2）上面（1）宏观调度的每一步，每一个AB点的连线，都要连续打印很多数
abPrint(arr, Ar, Ac, Br, Bc, fromAB);
//打印完A--B，或者B--A就要调度AB同步走
//最开始A的列Ac，Ac还没有到右边界M-1，则可以先往右增加，此时Ar不能变动，
//如果Ac=M-1，到右边界了，Ar才可以开始增加，A往下走，所以Ar的判断条件和走法是图中第三行的情况。
Ac = Ac == M - 1 ? Ac : Ac + 1;//Ac到右边界不能动
Ar = Ac == M - 1 ? Ar + 1: Ar;//这句得放前面
//类似的，
//最开始B的行Br，Br还没有到下边界N-1，则可以先往下增加，此时Bc不能变动，
//如果Br=N-1，到下边界了，Bc才可以开始增加，B往右走，所以Bc的判断条件和走法时图中的第四行的情况。
Br = Br == N - 1 ? Br : Br + 1;//到下边界就停
Bc = Br == N - 1 ? Bc + 1: Bc;//这句话得放前面！！！
//掉头扫描
fromAB = !fromAB;
}
//当AB相遇，下一次Ar就会越界的
}
public static void test(){
int[][] arr = {
{
1, 2, 3, 4, 5},
{
6, 7, 8, 9, 10},
{
11, 12, 13, 14,15}
};//打印1,2,6,11,7,3,4,8,12,13，9,5,10,14,15
zigzagPrintMatrix(arr);
System.out.println();
zigzagPrintMatrixReview(arr);
System.out.println();
wrongZigzagPrintMatrixReview(arr);
}
public static void main(String[] args) {
test();
}
由于Ac先更新，到右边界M-1，引发Ar+1，所以A斜着走了
由于Br先更新，到下边界N-1，引发Bc+1，所以B也斜着走了
导致矩阵很多地方没有被打印：
1 2 6 11 7 3 4 8 12 13 9 5 10 14 15
1 2 6 11 7 3 4 8 12 13 9 5 10 14 15
1 2 6 12 4 14 10 15
因此，一定记住了，把Ar的更新放在前面，把Bc的更新放前面，就能避免这个错误！
总结
提示：重要经验：
1）矩阵的zigzag扫描打印是图像工程中的一种编码方式，它的扫描打印代码是需要利用宏观调度的
2）AB从左上角，A先往右，B先往下，然后A往下，B往右，最后相遇结束，尤其要注意，Ar更新和Bc的更新，一定要放在Ac和Br的前面
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/9807.html
