题解 | #螺旋矩阵#

螺旋矩阵

https://www.nowcoder.com/practice/7edf70f2d29c4b599693dc3aaeea1d31

题意描述

给定一个m x n大小的矩阵(m行,n列),按螺旋的顺序返回矩阵中的所有元素。

数据范围:100n,m10,矩阵中任意元素都满足 val<=100
要求:空间复杂度 O(nm),时间复杂度 O(nm)

思路:

其实这道题就是一个简单的模拟,我们想象有一个矩阵,从第一个元素开始,往右到底后再往下到底后再往左到底后再往上,结束这一圈,进入下一圈螺旋。
  • step 1:首先排除特殊情况,即矩阵为空的情况。
  • step 2:设置矩阵的四个边界值,开始准备螺旋遍历矩阵,遍历的截止点是左右边界或者上下边界重合。
  • step 3:首先对最上面一排从左到右进行遍历输出,到达最右边后第一排就输出完了,上边界相应就往下一行,要判断上下边界是否相遇相交。
  • step 4:然后输出到了右边,正好就对最右边一列从上到下输出,到底后最右边一列已经输出完了,右边界就相应往左一列,要判断左右边界是否相遇相交。
  • step 5:然后对最下面一排从右到左进行遍历输出,到达最左边后最下一排就输出完了,下边界相应就往上一行,要判断上下边界是否相遇相交。
  • step 6:然后输出到了左边,正好就对最左边一列从下到上输出,到顶后最左边一列已经输出完了,左边界就相应往右一列,要判断左右边界是否相遇相交。
  • step 7:重复上述3-6步骤直到循环结束。
不过要注意一个小问题就是矩阵的行数会不等~~~~
// 注意矩阵行列数不相等
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> result;
        if (0==matrix.size())
            return result;
        int cols=matrix[0].size(), rows=matrix.size();
        int right=cols-1, down=rows-1, left=0, up=0;
        int i=0,j=0;							//原矩阵下标
        while (result.size() < cols*rows-1) {
            for (up++;j<right;j++)
                result.push_back(matrix[i][j]);
            if (result.size() == cols*rows-1) { //针对一行
                result.push_back(matrix[i][j]);
                return result;
            }
            for (right--;i<down;i++)
                result.push_back(matrix[i][j]);
            for (down--;j>left;j--)
                result.push_back(matrix[i][j]);
            if (result.size() == cols*rows-1) { //针对一列
                result.push_back(matrix[i][j]);
                return result;
            }
            for (left++;i>up;i--)
                result.push_back(matrix[i][j]);
        }
        result.push_back(matrix[i][j]);
        return result;
    }
};




全部评论

相关推荐

其实本来打算等lastday的时候再写的,但是现在提笔写下这篇总结完全是出于自己的想法,今天上午自己被学校发的签到吵醒时才突然想明白了很多事情,遂决定写下本文进行总结,虽然现在顶多算2.5个月,但也大差不差喵。回看这段时间的日常实习,我的关键词是:遗憾,焦虑。当然也有快乐的时候,不过大部分时间都是前面这两种情绪主导。为了避免后人再次踩坑,我将在本文详细解释我遇到的困难&nbsp;+&nbsp;产生的原因&nbsp;+&nbsp;应对的措施。同时总结新人实习时除了业务本身,还有如何处理生活与工作上的平衡,调控自身的情绪,让自己恢复到最好的工作状态。本文不会教你实习怎么去做产出,因为有产出的前提是你的心态足够健康,且在工作之余还有时间去...
wuwuwuoow:你的经历跟挺像,但我实力远没你强,现在只能干外包。但解决焦虑这块我应该比你更有经验,因为我曾经也非常迷茫和焦虑: 1.规律作息。无论节假日,都必须在同一时间点睡觉,同一时间点起床。放假睡的多,工作睡的少,这就是典型的作息不规律。将直接干扰前额叶皮层功能,导致情绪波动(易怒、焦虑)。无论上班还是周末,我都是 11:30 睡,7 点起床。7.5h 睡眠,完全足够了。 2.运动。缓解压力,强身健体,提高免疫力。不要觉得每天没有时间锻炼,都是懒惰的借口。 3.冥想。长期练习会增厚前额叶皮层(理性决策区),缩小杏仁核体积(减少情绪过敏反应,核心),增强情绪调控能力。 方法很简单,任何时候都能做。就是闭上眼睛,只专注自己的呼吸,不去想其他任何事情。你可以尝试一下,你会发现非常难只专注呼吸,会有大量的想法涌现出来(什么走马灯),不要去压抑它们,而是放平心态,把注意力继续放在呼吸上面。 而且最重要的是,冥想让你学会“活在当下”。因为处于冥想的你,除了专注呼吸你还能做什么呢?你什么都做不了。生活也是这样,我们无法改变过去,无法预知未来会发生什么,我们能做的只有手头的事情,除此之外什么都别想,因为你无法去改变它们。 4.工作与生活分离。工作不是生活的全部,生活可不是只有工作。像我放假的时候,从不带电脑回去。放假该玩就玩吧。 上面要是都能做到,其实完全解决不了你工作上的问题,完不成的需求还是完不成,面试该挂还是得挂。不过呢,当你再次迷茫,再次焦虑的时候,你会发现,诶,还好,没这么难受。比如面试挂了,可能以前的你会感觉非常难受。但如果你做到以上 4 点,你还是会难受的,但其实又没这么难受,可能你会这样想:既然挂了我还能怎么样?这公司不要我,有的是公司要我!
投递腾讯等公司6个岗位 >
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
4
4
分享

创作者周榜

更多
牛客网
牛客企业服务