​LeetCode刷题实战498:对角线遍历

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 对角线遍历,我们先来看题面:
https://leetcode-cn.com/problems/diagonal-traverse/
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
给你一个大小为 m x n 的矩阵 mat ,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。

示例                         

​LeetCode刷题实战498:对角线遍历


解题

https://blog.csdn.net/weixin_44171872/article/details/108579662

主要思路:
(1)确定每个对角线的特征,既x,y坐标之和逐渐的从0到 m+n 增长;
(2)然后确定每个对角线的起始位置,变换下一个位置时,通过对两个坐标值的加一或减一实现对下一个元素的遍历;
(3)确定每个遍历的终止条件,保证不会在数组范围内越界;

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
      //处理特殊的情形
        if(matrix.empty()||matrix[0].empty()){
            return {};
        }
        //初始化相关变量
        vector<int> res;
        int m=matrix.size();
        int n=matrix[0].size();
    //遍历数组
        int i=0;
        while(i<m+n){
          //从左下到右上的遍历
            int x=i<m?i:m-1;
            int y=i-x;
            while(x>=0&&y<n){//该趟遍历的终止位置
                res.push_back(matrix[x][y]);
                --x;
                ++y;
            }
            ++i;//跳转下一趟遍历

            if(i==m+n){//处理可能的越界
                break;
            }
            
      //从右上到左下
            y=i<n?i:n-1;
            x=i-y;
            while(y>=0&&x<m){//该趟遍历的终止位置
                res.push_back(matrix[x][y]);
                ++x;
                --y;
            }
            ++i;
        }
        return res;
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-480题汇总,希望对你有点帮助!

LeetCode刷题实战481:神奇字符串

LeetCode刷题实战482:密钥格式化

LeetCode刷题实战483:最小好进制

LeetCode刷题实战484:寻找排列

LeetCode刷题实战485:最大连续 1 的个数

LeetCode刷题实战486:预测赢家

LeetCode刷题实战487:最大连续1的个数 II

LeetCode刷题实战488:祖玛游戏

LeetCode刷题实战489:扫地机器人

LeetCode刷题实战490:迷宫

LeetCode刷题实战491:递增子序列

LeetCode刷题实战492:构造矩形

LeetCode刷题实战493:翻转对

LeetCode刷题实战494:目标和

LeetCode刷题实战495:提莫攻击

LeetCode刷题实战496:下一个更大元素 I

LeetCode刷题实战497:非重叠矩形中的随机点


​LeetCode刷题实战498:对角线遍历

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/18404.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息