欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-02 20:10:43
话不多说,先上题!给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。解题思路本题最关键的地方就是发现对角线遍历的规律再考虑特殊情况。通过观察我们可以发现遍历规律为(设定层数 = 行数 + 列数):当前元素的层数为偶数时,遍历箭头指向右上方;当前元素的层数为奇数时,遍历箭头指向左下方。对应的伪代码即为:if((r+c)) % 2) == 0r–; c++;elser++; c–;而特殊情况则是:当层数为偶...

话不多说,先上题!
给定一个含有 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