对角线遍历矩阵

C++ 解法, 执行用时: 6ms, 内存消耗: 1192KB, 提交时间: 2022-02-10

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> diagonalOrder(vector<vector<int> >& mat)
    {
        int m = mat.size();
        int n = mat[0].size();
       
        vector<int> ret;
        int topRight_x = 0, topRight_y = 0; //沿着最上顶行朝右走，直至碰到最右列
        int downLeft_x = 0, downLeft_y = 0; //沿着最左顶列朝下走，直至碰到最下行
        
        bool starFromUP = false;
        ret.push_back(mat[0][0]);
        while(topRight_y < n && topRight_x < m && downLeft_y < n &&downLeft_x < m)
        {
            if(topRight_y + 1 < n)
                ++topRight_y;
            else
                ++topRight_x;
            
            if(downLeft_x + 1 < m)
                ++downLeft_x;
            else
                ++downLeft_y;
            
            starFromUP = !starFromUP;
            appendElement(starFromUP, mat, ret, topRight_x, topRight_y, downLeft_x, downLeft_y);
        }
        
        return ret;
    }
    
    void appendElement(bool starFromUP, vector<vector<int>> &mat, vector<int> &ret, int x1, int y1, int x2, int y2)
    {
        if(starFromUP)
        {
            while(x1 <= x2)
                ret.push_back(mat[x1++][y1--]);
        }
        else
        {
            while(y2 <= y1)
                ret.push_back(mat[x2--][y2++]);
        }
    }
};

C++ 解法, 执行用时: 7ms, 内存消耗: 1188KB, 提交时间: 2022-01-24

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> diagonalOrder(vector<vector<int> >& mat) {
        // write code here
        vector<int> res;
        if(mat.size()==0) return res;
        if(mat.size()==1) {//当mat长度为1，说明mat里面只有一个数组
            for(int i=0;i!=mat[0].size();++i) res.push_back(mat[0][i]);
            return res;
        }
        if(mat[0].size()==1) {//当mat[0]长度为1，说明只有1列
            for(int i=0;i!=mat.size();++i) res.push_back(mat[i][0]);
            return res;
        }
        int m=mat.size()-1;
        int n=mat[0].size()-1;
        res.push_back(mat[0][0]);
        int i=0,j=1;
        while(i<=m||j<=n) {//退出循环条件是当i=m&&j=n
            //当i=0或j=n且(i+j)是奇数时，斜向下遍历直到j=0或i=m
            if(((i==0||j==n)&&(i+j)&1)){
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                while(j>0&&i<m) res.push_back(mat[i][j]),++i,--j;
            }
            //当i=0或j=n且(i+j)是偶数时，如果j<n，直接++j;否则++i
            else if((i==0||j==n)&&(i+j)%2==0){
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                if(j<n) res.push_back(mat[i][j]),++j;
                else res.push_back(mat[i][j]),++i;
            }
            //当j=0或i=m且(i+j)是奇数时，如果i<m，++i；否则++j
            if((j==0||i==m)&&(i+j)&1) {
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                if(i<m) res.push_back(mat[i][j]),++i;
                else res.push_back(mat[i][j]),++j;
            } 
            //当j=0或i=m且(i+j)是偶数时，斜向上遍历直到i=0或j=n
            else if((j==0||i==m)&&(i+j)%2==0){
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                while(i>0&&j<n) res.push_back(mat[i][j]),--i,++j;
            }
        }
        return res;
    }
};

C++ 解法, 执行用时: 7ms, 内存消耗: 1200KB, 提交时间: 2022-01-18

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> diagonalOrder(vector<vector<int> >& mat) {
        // write code here
        vector<int> result;
        int rows=mat.size();
        int cols=mat[0].size();
        result.reserve(rows*cols);
        int i=0;
        int j=0;
        int pos=0;
        while(i<rows&&j<cols)
        {
            result.push_back(mat[i][j]);
            int x=i;
            int y=j;
            for(int k=0;k<3;++k)
            {
                i=x+dx[pos][k];
                j=y+dy[pos][k];
                if(i>=0&&j>=0&&i<rows&&j<cols)
                {
                    if(k>0)
                        pos^=1;
                    break;
                }
            }
        }
        return result;
    }
    private:
    const int dx[2][3]={{-1,0,1},{1,1,0}};
    const int dy[2][3]={{1,1,0},{-1,0,1}};
};

C++ 解法, 执行用时: 7ms, 内存消耗: 1280KB, 提交时间: 2021-12-08

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> diagonalOrder(vector<vector<int> >& mat) {
        vector<int> result;
        int rows=mat.size();
        int cols=mat[0].size();
        result.reserve(rows*cols);
        int i=0;
        int j=0;
        int pos=0;
        while(i<rows && j<cols) {
            result.push_back(mat[i][j]);
            int x=i;
            int y=j;
            for(int k=0;k<3;++k) {
                i=x+dx[pos][k];
                j=y+dy[pos][k];
                if(i>=0 && j>=0 && i<rows && j<cols) {
                    if(k>0) pos^=1;
                    break;
                }
            }
        }
        
        return result;
    }
    
private:
    const int dx[2][3]={{-1,0,1}, {1,1,0}};
    const int dy[2][3]={{1,1,0}, {-1,0,1}};
};

C++ 解法, 执行用时: 7ms, 内存消耗: 1288KB, 提交时间: 2022-03-14

class Solution {
public:
    
    vector<int> diagonalOrder(vector<vector<int>>& mat) {
        vector<int> res;
        vector<int> t;//临时数组
        if(mat.size()==0)
            return res;
        int n=mat.size(),m=mat[0].size();
        
        int flag=1;//-1表示斜向上，1表示斜向下
        int i=0;
        for(;i<n;i++){//遍历前n行
            flag=-flag;
            for(int j=0;j<m&&j<=i;j++){//遍历行中元素
                t.push_back(mat[i-j][j]);
            }
            if(flag==1)
                reverse(t.begin(),t.end());
            for(int j=0;j<t.size();j++)
                res.push_back(t[j]);
            t.clear();
        }
        int tmp=0;
        for(;i<n+m-1;i++){//遍历后面的行
            flag=-flag;
            for(int j=++tmp;j<tmp+n&&j<m;j++){//遍历行中元素
                t.push_back(mat[i-j][j]);
            }
            if(flag==1)
                reverse(t.begin(),t.end());
            for(int j=0;j<t.size();j++)
                res.push_back(t[j]);
            t.clear();
        }
        return res;
    }
};

详情