数组与字符串——对角线遍历

话不多说，先上题！
给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

解题思路

• 本题最关键的地方就是发现对角线遍历的规律再考虑特殊情况。通过观察我们可以发现遍历规律为（设定层数 = 行数 + 列数）：当前元素的层数为偶数时，遍历箭头指向右上方；当前元素的层数为奇数时，遍历箭头指向左下方。
  对应的伪代码即为:

if((r+c)) % 2) == 0
r–; c++;
else
r++; c–;

• 而特殊情况则是：当层数为偶数时，如果元素处于最后一列时无法继续向上遍历，此时需要向下移动一格，准备向下遍历，如果元素处于第一行时需要向右移动一格，准备向下遍历。当层数为奇数时，如果元素处于第一列需向下移动一格，准备向上遍历，如果元素处于最后一行时，需向右移动一格，准备向上遍历。

代码

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> v;
        if(matrix.size() == 0 || matrix[0].size() == 0) {
            return v;
        }
        int row = matrix.size();
        int column = matrix[0].size();
        int r = 0, c = 0;
        //核心：1.找出对角线遍历方向随坐标变化的规律；2.特殊情况特殊处理
        int num = row*column;
        for(int i = 0; i < num; i++) {
            v.push_back(matrix[r][c]);
            //(r+c)为遍历的层数，奇数为向下遍历，偶数为向上遍历
            if((r+c) % 2 == 0) {
                if(c == column - 1) {
                    //处于最后一列
                    //向下移动一格，准备向下遍历
                    r++;
                } else if(r == 0) {
                    //处于第一行
                    //向右移动一格，准备向下遍历
                    c++;
                } else {
                    r--;
                    c++;
                }
            } else {
                if(c == 0) {
                    //处于第一列
                    //向下移动一格，准备向上遍历
                    r++;
                } else if(r == row - 1) {
                    //处于最后一行
                    //向右移动一格，准备向上遍历
                    c++;
                } else {
                    r++;
                    c--;
                }
            }
        }
        return v;
    }
};

本文地址：https://blog.csdn.net/qq_43830731/article/details/107595274