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!