C++打印之字形矩阵

打印之字形矩阵

1. 题目描述

给定一个矩阵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额外空间复杂度为 O ( 1 ) O(1) O(1).

2. 解题思路

这题如果扣下标的关系的话将很难写,会陷入局部关系.但是我们从整体出发思路就会开阔很多.和前面的类似,本题采用的方法也是化整为零.

1. 上坐标（tR，tC）的初始为（0,0），先沿着矩阵的第一行移动（tC++）,当达到第一行最右边的元素后，再沿着矩阵最后一列移动 (tR++)。
2. 下坐标（dR，dC）的初始为（0,0），先沿着矩阵的第一列移动（dR++），当到达第一列最下边的元素时，再沿着矩阵的最后一行一定（dC++）。
3. 上坐标与下坐标同步移动，每次移动后的上坐标与下坐标的连线就是矩阵中的一条斜线，打印斜线上的元素即可。
4. 如果上次斜线是从左下向右上打印的，这次一定是从右上向左下打印，反之亦然。总之，可以把打印的方向用bool变量表示，每次取反即可。

3. c++代码

#include <iostream>
#include <vector>

template<typename T>
void printLevel(std::vector<std::vector<T>>& my_matrix,
                int tR, int tC, int dR, int dC, bool updown) {
    if (updown) {
        while (tR != dR + 1) {
            std::cout << my_matrix[tR++][tC--] << ",";
        }
    } else {
        while (dR != tR - 1) {
            std::cout << my_matrix[dR--][dC++] << ",";
        }
    }
}

template<typename T>
void printMatrixZigZag(std::vector<std::vector<T>>& my_matrix) {
    int tR = 0;
    int tC = 0;
    int dR = 0;
    int dC = 0;
    bool updown = false;
    int endR = my_matrix.size() - 1;
    int endC = my_matrix[0].size() - 1;
    while (tR != endR + 1) {
        printLevel(my_matrix, tR, tC, dR, dC, updown);
        tR = tC == endC ? tR + 1 : tR;
        tC = tC == endC ? tC : tC + 1;
        dC = dR == endR ? dC + 1 : dC;
        dR = dR == endR ? dR : dR + 1;  // attention here
        updown = !updown;
    }
    std::cout << "\n";

}

template<typename T>
void printMatrix(std::vector<std::vector<T>>& my_matrix) {
    for (int i = 0; i < my_matrix.size(); ++i) {
        for (int j = 0; j < my_matrix[0].size(); ++j) {
            std::cout << my_matrix[i][j] << ",";
        }
    }
}
int main() {
    std::vector<std::vector<int>> my_matrix = {{1, 2, 3, 4},
                                               {5, 6, 7, 8},
                                               {9, 10,11,12}};
    std::cout << "origin matrix is:" << std::endl;
    printMatrix(my_matrix);
    std::cout << "\n";
    std::cout << "zigzig matrix is:" << std::endl;
    printMatrixZigZag(my_matrix);

    return 0;
}

           

4. 一点注意

这里我们在写主函数4个点的更新代码的时候需要注意前后顺序, 原始代码:

tR = tC == endC ? tR + 1 : tR;
   tC = tC == endC ? tC : tC + 1;
   dC = dR == endR ? dC + 1 : dC;
   dR = dR == endR ? dR : dR + 1;  // attention here
           

一开始我把第三行和第四行,写反了,即写成:

tR = tC == endC ? tR + 1 : tR;
   tC = tC == endC ? tC : tC + 1;
   dR = dR == endR ? dR : dR + 1;  // attention here
   dC = dR == endR ? dC + 1 : dC;
  
           

然后程序死活得不到正确结果,因为感觉思路也是对的,为什么不能得到正确结果了.然后我们就进行了debug操作.

从debug操作我们知道,在程序进行跑到第三轮的时候,代码第三行其实dR被更新了,从而导致第四行的条件判断已经到边界了,所以此时dC变成了1,但实际上我们需要此时dC=0才对.因此第3,4行代码是不可交换的.

5. 参考文献

1. [算法]“之”字形打印矩阵
2. C++ 打印之字形矩阵

debug是个好东西,mark!