153.Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

有一个排好序的数组,可能从中间某个元素开始有环形存在,假设不存在重复元素,请找出其中的最小值。

第一眼看到这道题的时候我直接对数组进行了遍历,然后维护一个min指针指向数组中的最小元素,AC之后看了一下时间只用了4ms,觉得时间性能还不错,代码如下:

/*solution1*/
class Solution {
public:
    int findMin(vector<int>& nums) {
        int size=nums.size();
        int i=0,min=0;
        for(i=0;i<size;i++){
            if(nums[i]<nums[min])
                min=i;
        }
        return nums[min];
    }
};

不过看了讨论区之后觉得自己的答案和大牛们比起来简直太小学生了,上面的算法时间复杂度为O(n),而大牛们通过使用binary_search将时间复杂度降低到了O(lgN).下面我来简述一下binary search解决此题的思路。

因为是排好序的数组,所以只需要分为三种情况

  1. [0,1,2,3,4,5,6,7]这种情况的特征是最左边的值小于最右边,所以最左边的一定是minimum,直接返回。
  2. [4,5,6,7,0,1,2,3]这种情况的特征是中间的数大于最右边的数,所以minimum一定出现在右半区中,调整到右半区继续查找。
  3. [5,6,7,0,1,2,3,4]这种情况的特征是中间的数小于最左边的数,所以minimum一定出现在左半区中,调整到右半区继续查找。 代码如下:
/*solution2*/
class Solution {
public:
    int findMin(vector<int>& nums) {
        int size=nums.size(),low=0,high=size-1,mid=0;
        while(low<high){
            if(nums[low]<nums[high])
                return nums[low];
            mid=(low+high)/2;
            if(nums[mid]>nums[high])
                low=mid+1;
            else
                high=mid;
        }
        return nums[low];
    }
};

代码AC之后,我查看了运行时间,还是4ms,时间上没有太大的改变,应该是和测试用例有关,但时间复杂度降低到了对数级,在数据量较大的时候应该就能显示出来差异了。

118.Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,

Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

给出行数,要求生成杨辉三角。

这道题只要找到了从第二行开始的递推公式即可,我们发现最左和最右两个数都是1,中间的数等于其“肩上”两数之和。根据组合数公式 image ,对于第k(k > 2)层第n(n > 1 && n < k)个元素A[k][n]有

A[k][n] = A[k-1][n-1] + A[k-1][n]

image

由此我们可以写出代码如下:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> val;
        val.resize(numRows);
        int i=0,j=0;
        for(i=0;i<numRows;i++){
            val[i].resize(i+1);
            val[i][0]=1;
            val[i][val[i].size()-1]=1;
            for(j=1;j<val[i].size()-1;j++)
                val[i][j]=val[i-1][j-1]+val[i-1][j];
        }
        return val;
    }
};
  • [ TODO 119. Pascal’s Triangle II ]

大家好!

各位都非常年轻,我今天来的时候挺有压力。因为我毕业快11年了,看到你们,真是觉得“长江后浪推前浪”。

我去年参加了武汉的校招,感觉新一代年轻人的素质确实都非常好。我昨天就在想,今天应该跟大家分享什么。想了想,先把题目拟出来,把乔布斯的“Stay hungry, Stay foolish”,改成“Stay hungry, Stay young”。

我想跟大家分享一下我自己毕业后的工作经历和体会。另外,我作为面试官,过去10年里,可能面试过小2000个年轻人。有的和我在一家公司,有的去了别家公司,他们发展差别其实非常大。从算法层面上讲,我们把这叫做“正例”和“负例”。我想分享一下:为什么“正例”和“负例”发展差别这么大?

什么是“Stay hungry, Stay young”?“Stay hungry”,大家都知道,就是好奇心、求知若渴、上进心。但为什么要说“Stay young”?

我觉得年轻人有很多优点:做事不设条条框框,没有太多自我要维护,经常能打破常规,非常努力、不妥协、不圆滑世故。

10年过去了,有的年轻人,依然保持着这些很好的特质。我觉得这就算“Stay young”。

“Stay young”的人基本没有到天花板,一直保持着自我的成长。相反,很多人毕业后提高了技能,但到一个天花板后,就不再成长了。

我先分享一下自己毕业后的个人经历。

2005年,我从南开大学毕业,加入了一家公司叫酷讯。我是最早期加入的员工之一,一开始只是一个普通工程师,但在工作第二年,我在公司管了四五十个人的团队,负责所有后端技术,同时也负责很多产品相关的工作。有人问我:为什么你在第一份工作就成长很快?是不是你在那个公司表现特别突出?

其实不是。当时公司招聘标准也很高。跟我同期入职的,我记得就有两个清华计算机系的博士。

那我是不是技术最好?是不是最有经验?我发现都不是。后来我想了想,当时自己有哪些特质。

第一个,我工作时,不分哪些是我该做的、哪些不是我该做的。我做完自己的工作后,对于大部分同事的问题,只要我能帮助解决,我都去做。当时,Code Base中大部分代码我都看过了。新人入职时,只要我有时间,我都给他讲解一遍。通过讲解,我自己也能得到成长。

还有一个特点,工作前两年,我基本上每天都是十二点一点回家,回家以后也编程到挺晚。确实是因为有兴趣,而不是公司有要求。所以我很快从负责一个抽取爬虫的模块,到负责整个后端系统,开始带一个小组,后来带一个小部门,再后来带一个大部门。

另外还有一点:做事不设边界。当时我负责技术,但遇到产品上有问题,也会积极地参与讨论、想产品的方案。很多人说这个不是我该做的事情。但我想说:你的责任心,你希望把事情做好的动力,会驱动你做更多事情,让你得到很大的锻炼。

我当时是工程师,但参与产品的经历,对我后来转型做产品有很大帮助。我参与商业的部分,对我现在的工作也有很大帮助。记得在07年底,我跟公司的销售总监一起去见客户。这段经历让我知道:怎样的销售才是好的销售。当我组建头条招人时,这些可供参考的案例,让我在这个领域不会一无所知。

以上就是我刚毕业时的特点。

后来,我陆续加入到各种创业团队。在这个过程中,我跟很多毕业生共处过,现在还和他们很多人保持联系。跟大家分享一下,我看到的一些好和不好的情况。总结一下,这些优秀年轻人有哪些特质呢?

第一,有好奇心,能够主动学习新事物、新知识和新技能。今天不太谦虚,我把自己当做正例,然后再说一个负例。我有个前同事,理论基础挺好,但每次都是把自己的工作做完就下班了。他在这家公司呆了一年多,但对网上的新技术、新工具都不去了解。所以他非常依赖别人。当他想要实现一个功能,他就需要有人帮他做后半部分,因为他自己只能做前半部分——如果是有好奇心的人,前端、后端、算法都去掌握、至少有所了解的话,那么很多调试分析,自己一个人就可以做。

第二,对不确定性保持乐观。比方说头条最开始时,我跟大家讲:我们要做1亿的日启动次数。(当然,现在不止1亿了,我们现在的日启动次数已经差不多5亿。)很多人觉得,你这家小公司怎么可能做得到呢?大公司才能做得好。所以他就不敢努力去尝试。只有乐观的人会相信,会愿意去尝试。其实我加入酷讯时也是这样。那家公司当时想做下一代搜索引擎(最后也没有做成,只做了旅游的垂直搜索)。我不知道其他人怎么想的,我自己觉得很兴奋。我确实没有把握,也不知道怎么做,但当时就去学,就去看所有这些相关东西。我觉得最后也许不一定做成,或者没有完全做到,但这个过程也会很有帮助——只要你对事情的不确定性保持乐观,你会更愿意去尝试。

第三,不甘于平庸。我们在座各位,在同学中已经非常优秀了。但我想说,其实走向社会后,应该再设定更高的标准。我见到很多大学期间的同学、一起共事的同事中,有很多非常不错的人才,技术、成绩都比我好。但10年过去,很多人没有达到我的预期:我觉得他应该能做得很好,但他却没有做到。

很多人毕业后,目标设定就不高了。我回顾了一下,发现有同事加入银行IT部门:有的是毕业后就加入,有的是工作一段时间后加入。为什么我把这个跟“不甘于平庸”挂在一起呢?因为他们很多人加入,是为了快点解决北京户口,或者当时有些机构有分房补助,可以购买经济适用房。

后来我就在想一个问题,如果自己不甘于平庸,希望做得非常好的话,其实不会为这些东西担心:是否有北京户口,是否能买上一套经济适用房?如果一个人一毕业,就把目标定在这儿:在北京市五环内买一个小两居、小三居,把精力都花在这上面,那么工作就会受到很大影响。

他的行为会发生变化,不愿意冒风险。比如我见到以前的朋友,他业余做一些兼职,获取一些收入。那些兼职其实没有什么技术含量,而且对本职工作有影响,既影响他的职业发展,也影响他的精神状态。我问他为什么,他说,哎,快点出钱付个首付。我觉得他看起来是赚了,其实是亏的。

不甘于平庸很重要。我说不平庸,并不是专门指薪酬要很高或者技术很好,而是你对自己的标准一定要高。也许你前两年变化得慢,但10年后再看,肯定会非常不一样。

第四,不傲娇,要能延迟满足感。我在这里举个反例:两个我印象比较深刻的年轻人,素质、技术都蛮不错,也都挺有特点。我当时是他们的主管,发现他们在工作中deliver的情况始终不好。他觉得其他同事比他做得差,其实不是:他们确实可以算作在当时招的同事里面TOP 20%,但他们觉得自己是TOP 1%。所以很多基础一点的工作,比如要做一个调试工具,他就不愿意做,或者需要跟同事配合的工作,他就配合得不好。

本来都是资质非常好的人才,人非常聪明、动手能力也强,但没有控制好自己的傲娇情绪。我觉得这和“不甘于平庸”不矛盾。“不甘于平庸”是你目标要设得很高,“不傲娇”是你对现状要踏实。

这2000个样本当中,我见到很多我原来觉得很好的,其实没有我想象中的发展好,我原来觉得不好的,其实超出我的预期。这里我也举个例子。当时我们有个做产品的同事,也是应届生招进来,当时大家都觉得他不算特别聪明,就让他做一些比较辅助的工作,统计一下数据啊做一下用户反弹啊之类。但现在,他已经是一个十亿美金公司的副总裁。

后来我想想,他的特点就是肯去做,负责任,从来不推诿,只要他有机会承担的事情,他总尽可能地做好。每次也不算做得特别好,但我们总是给他反馈。他去了那家公司后,从一个用户量不到10万的边缘频道负责起来,把这个频道越做越好。由于这是一个边缘频道,没有配备完整的团队,所以他一个人承担了很多职责,也得到了很多锻炼。

第五,对重要的事情有判断力。选什么专业、选什么公司、选什么职业、选什么发展路径,自己要有判断力,不要被短期选择而左右。上面一些例子,也都涵盖了这一点。比如当时很多人愿意去外企,不愿意去新兴的公司。06、07年,很多师弟、师妹问我职业选择,我都建议他们去百度,不要去IBM、微软。但实际上,很多人都是出于短期考虑:外企可能名气大、薪酬高一点。虽然这个道理,大家都听过很多遍。刚毕业时薪酬差三五千块,真的可以忽略不计。短期薪酬差别并不重要。但实际上,能摆脱这个、能有判断力的人,也不是特别多。

这些就是我想跟大家分享的。

谢谢!

徐鹏——代码改变世界

这个ppt是我昨天晚上两点多写的,大家可见RD的生活是什么样的。我想说的是,程序员是最讲究优雅的,可能他穿一个拖鞋,但可能他写的代码非常的优雅;你会发现他的博客上会非常的精美,所以我觉得优雅不优雅不一定在于一个人的外表,而在于看他做的事。

我叫徐鹏,我是今日头条的工程师。如果在大学的时候有人告诉我有人要回北邮给大家讲怎么做技术,我觉得那完全是扯淡的。我告诉大家肯定不可能,因为我在大学的时候觉得我不会去做技术,因为我觉得自己可能不太合适做技术。到研究生之后,我慢慢的也因为一些不知名的原因坚持做了技术,然后我发现技术是有它的魅力在里面的。

就是大家在做一个事情的时候,在你没有做好的时候,有可能会去怀疑自己是不是适合做这个事情,比如说很多人在刚开始编程的时候认为之前没有接触过,他在做的时候会说觉得自己不适合编程。其实有可能你做了产品经理之后也觉得自己不适合做产品经理。其实这不是一个借口,如果你没有发现自己适合做什么,你就应该去尝试做一个东西。你觉得自己不适合编程,那你有用心编过程吗?你有用心的做过这个事情吗?你没有用心的做过,你怎么知道自己做不好呢?

第一 我要讲的是“知道or不知道” 有四种情况:你知道你知道;你不知道你知道;你知道你不知道;你不知道你不知道。知道知道很好讲,不知道知道也很容易讲;知道不知道,比如说我知道C++,但是我不会,这叫知道不知道;不知道不知道就是你不知道自己不知道。但是不知道不知道是会影响你的轨迹的,比如你不知道你自己是一个天才,但是如果有人告诉你,这个事情该怎么去做,那么你就能把它做好。所以影响大家check的就是你不知道你不知道。所以今天就重点给大家讲讲你不知道你不知道的东西。

1、软实力——上手能力很重要 其实我今天不太想给大家讲找工作的东西,找工作的东西大家都比较清楚,其实更想讲的是让大家在大学里时间很充裕的时候成为一个真正的工程师,全名叫软件工程师。成为一个工程师需要什么东西?一个叫软实力,一个叫硬实力。什么叫软实力,我进了头条之后会面很多BAT的工程师,但是有很多他简历上非常优秀的东西在我们这边都是没有用的,是他的硬实力不好吗?C++、HTML5都不明白吗?JAVA虚拟机搞不清楚吗?不是的,是第一个软实力不行。一个工程师最重要的是什么?我告诉大家,叫上手能力。

什么叫做上手能力?我现在举一个例子,就是我布置给大家一个作业,要大家用JAVA去编一个很简单的东西,就写一个hello,world!有的同学可能会在别人dota一把的时间他就把这个搞定了,有些人可能搞了一个星期、一个月都没把它搞定,这就叫上手能力。这个东西怎么练,有些人说自己搞JAVA,“哇塞,我JDK装了好久,都要崩溃了,我装了一个星期,把所有的坑都踩了一遍。”然后呢,最后没装好,就告诉自己:“我不适合做编程。”这就是错误的,其实没有人生下来上手能力就是好的,所有人所经历的东西都是这样的,就是一个人从不会写代码到他写代码写的非常好,这个过程一定是很痛苦的。但是每个人对于痛苦的耐受力是不一样的。就跟有些人他长跑很厉害,能跑二十公里、四十公里甚至能跑马拉松,而有些人像我一样,只能跑三圈,就是我们对于跑步的耐受力不行。这就是软实力。就是你对一个工程,对一个技术,你对它的容忍,你在遇到坑的时候解决问题的能力,这个叫软实力。

知道软实力之后怎么去锻炼呢? just do it! Just do IT! 就是要去做,一定要去动手,一定要有那种钻研的精神把它搞出来。如果你做JAVA,你会发现,你第一次run的时候会有一点问题,第二次run的时候会有一点问题,但是慢慢的到后来这个问题一定会收敛的,收敛到你可控的范围内,到那个时候你就告诉自己,JAVA方面的东西我可以handle了。当你在玩python你发现python也就那么回事儿,东西都是相通的。所以这个东西叫软实力,很重要。

2、内功和外功 我一直觉得程序员像行走于江湖的剑客,每个人都有自己的一门独门绝技,或者有些人你会发现他内力极其深厚,让他去掌握一门武功的时候,他能在很短的时间内就把它掌握,而且玩得非常好,可能比一个专家玩的都好。什么叫内功呢?对于程序员来说有些东西是无法在短期内突击的,比如说一些工具Linux,没有人说我Linux玩了一段时间、用了三个月之后我成为了专家了,这不可能。

就是说像Linux这样的工具类的东西是有一个很陡的曲线在那儿,这个东西往往需要你真正的去使用它很长时间你才能把它搞好。但是如果你不去用它,你永远学不会。所以说解决内力的东西,凡是优雅的东西,都会比较难用。这个东西怎么去解决?就是去用它。去放下心来去来练你的内力。当你发现你的内力层很好的时候,你会发现自己做的很多框架类的东西其实都是相通的,你会发现很多模式都是有迹可寻的,到这个时候你的上手能力就会非常快。

Ok,当你把这两件事做好之后呢,你会发现有些人会成为好的工程师,有些人会成为一般的工程师,有些人可能慢慢地会掉队,成为不知道什么样的工程师。什么叫好的工程师?我觉得在座的各位都能够成为一个非常好的工程师,我给大家简单讲一下我的经历,其实我在老师这边真正深入的东西也不多,但是我发现有一个非常好的东西叫open source,也就叫开源。

第二 要真正自己去做一些东西 所以在做好前两件事情之后一个非常好的捷径就是我希望大家能够真正自己去做一些东西,很多人写简历的时候,会觉得自己简历上没有好的项目,是因为实验室导师做的东西我不感兴趣,或者说他做的东西没意思,这个东西不是一个借口。对于北邮人来说,我们其实能轻松地在网上搜到非常好的开源项目。比如说老师让你写仿真,但是你喜欢做网站,那么现在网站用什么东西呢?有人告诉你,用spring、struts但是你去搜索发现国外的人已经不用这些东西了,国外已经开始用NodeJS,那么你是不是可以去做更喜爱的方面的东西呢?所以这些东西就是你自己去探索,其实很多东西机会是我们自己去发现的。

不知道大家知不知道阿里在招聘的时候,有一个叫阿里星计划,应该是给一个应届生百万年薪,上一届的阿里星计划是给一个清华大学的本科生,拿到了阿里星的offer,但是最后他没去,他去了facebook。那么我们看一下这个人的简历上面有些什么呢?首先他建立的最上面就是他的github,我看到大部分人都是茫然的表情,可能不知道github,可能知道但是没有注册。

我现在告诉大家,你们今天回去第一件事情,不是拖鞋,就是先把github搞定,因为github是你和所有优秀的人沟通的一个桥梁,你们在github上看到国外最优秀的人写的代码。你有可能就不需要我在这讲了,你能看到这些人写的代码,你为什么还不能进步呢?他有非常好的架构模式,当你看了足够多这样优秀的代码,你去面试的时候,别人让你在web写段代码的时候,你洋洋洒洒写出了Justin写过的一段代码。面试官可能看了大半天,还不好意思问这是什么意思但是又觉得你写的是对的的时候,你距离你的offer就非常近了。

所以说现在,把github用起来。好,再继续刚才那个星计划的人,他自己就在github开展了很多个项目。当然大家可能会疑惑他这么牛逼的人会在开源上做什么项目呢?其实就是一些非常简单的项目,可能就是非常喜欢一个模式,做了一个模式的外挂,也有可能是你自己做了一个cs的例图,这些都可以放上去。

是要开始用心的经营自己,要把自己技术的这一块经营起来,这是第一点。第二点就是他在大学的时候就写过一本基础的书籍,国内第一NodeJS书是本科生写出来的,当然他是清华大学的本科生,怎么一个清华的本科生就能教这么多互联网公司、这么牛逼的工程师写NodeJS呢?因为那些人他们还不知道这个东西,而他已经学了很久,早就用起来了。所以他拿到了阿里星。

第三 当你真正想做技术的时候,应该怎么做 总结一下,当你真的觉得自己想要尝试去做一做技术的时候,其实这个check还是很简单的。

1、练好内功和外功 内功包括什么,就是你要去用一些令你恐惧的东西,不论是男孩子、女孩子还好,可能觉得我编程的时候觉得很恐惧,每次刷题,每次提交超市的时候会很恐惧,要战胜那种恐惧,现在就开始做起来,这一点特别重要。这里面就包括,掌握一门编程的语言。

2、做一个简单的项目 这个项目可以是什么呢?有可能是导师安排你的一些任务,也有就是你在github发现的非常简单写的非常优雅的项目拿回来自己读,当你读过一个或两个项目会发现这些东西之间有很多相通之处。你会慢慢找到里面的关联的点,那个时候就是你精进的时候。再到之后你有可能会有自己的一些想法,想去做一些东西,这个时候不要犹豫,只要是动手去做,把这个东西做出来,就有成功的基础了。

第四 一些踩到的坑 还有就是踩到的一些坑,我不知道大家刚开始编代码的时候是什么样的,其实我在本科的时候也没怎么好好写过代码,我是到研一的时候才开始写代码的,开始写的JAVA,然后我毕业四年,我居然出了一本技术的书,而且是一个极其复杂的框架的书,这是为什么呢,这其中其实也踩到了很多的坑。

我认为当你觉得自己不想做技术、不想去尝试的时候,或者说有一些犹豫的时候,可以想想,徐鹏他都搞技术了,我也可以搞一搞。一些踩到的坑技术层面的东西我不会讲太多,难点其实并不在那个地方,其实更多的是在于我们的一些想法,就是当你遇到一个问题,当你遇到一个你觉得自己无法解决的问题的时候,你是放弃还是继续,这个就影响了很多人。可能你到了一个临界点,下一条编译你就成功了,但你在这条命令上放弃了,那么你永远get不到这个点,这是第一。

第二我们不能惧怕问题,因为你是一个工程师,你要带着解决问题的态度把这个问题解决了,一定要抱着这种态度,而不是说遇到这个问题之后说我靠我怎么这么倒霉啊,他们拿过去一装就好了,我拿过来装就好多问题,如果这么想,那就完蛋了。第三,现在在座的工程师要有一点open的态度,open就是要跟别人多去交流,这个交流不止于你和你的同学之间的交流、跟你的舍友之间的交流,这个交流包括和国外的很多工程师的一些交流。怎么去交流?现在都有网站,你用过的一些小的东西你可以到开源社区里做一些反馈,你可以提一些自己的想法,我相信大家的英文简单的交流都是没有问题的,你可用简单的对话谈谈你自己的想法。Open的态度是非常重要的。

第五 从现在开始改变 Ok,前面我不会跟大家讲太多找工作方面的事情,我希望总结几点,希望大家从这个教室走出去回去以后,你能有所改变。第一,优秀的工程师的成长尽管有天赋的因素,但大部分人都是很普通的,优秀的人与普通人相比在于他的上限会高,但是下限是我们每个人都能不断提高的,不断的提高自己的下限,知道自己能做什么。

第二,那怎么样去提高它,就是做你害怕的事情,做你在技术上面你觉得害怕的事,不要觉得麻烦,去把它做好,去一点一点踩该踩的坑,把遇到的问题一个一个解决。当你坚持了三个月甚至是半年你就会发现,编程好像没那么难。

第三点呢,多去交流,今天晚上回去就可以注册github的账户,在那个上面找到非常多优秀的项目,优秀的想法。第四个,我建议大家开一个个人的技术博客,研究生的时候我发现很多工程师都来自于中科院,讲真我觉得北邮的学生编的比他们快也比他们好,我就和实验室的两个来自中科院的师兄去请教,我才发现他们每个人都有个人的技术博客,从博客的内容真的能感受到一种对技术的钻研和热爱。所以你现在也可以开始培养这样的习惯。

希望大家不要觉得编程有多难,为什么我选择编程,因为我觉得它简单纯净,就是靠技术说话,所以我的leader比我年龄小,但是我服,因为他的技术够牛逼。

谢谢大家。

54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5]

题目要求按照螺旋线的顺序对一个矩阵 进行遍历,目的和方法很明确,就是先在一行上从左向右遍历,再从行的末端从上到下遍历…………不再赘述。

问题的关键在于确定好循环的边界,那么我们引入up down left right作为每次遍历的边界,初始时分别指向第一行,最后一行,第一列,最后一列。那么在循环过程中,这四个值的变化情况为:

  1. 对最上一行遍历之后,up++
  2. 对最右边一列遍历之后,right–
  3. 对最下一行遍历之后,down–
  4. 对最左列进行遍历后,left++

代码具体如下:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) 
            return {};
        int row=matrix.size(),col=matrix[0].size();
        int up=0,down=row-1,left=0,right=col-1,k=0,i=0;
        vector<int> res(row*col);
        while(1){
            for(i=left;i<=right;i++)
                res[k++]=matrix[up][i];
            if(++up>down)
                break;
            
            for(i=up;i<=down;i++)
                res[k++]=matrix[i][right];
            if(--right<left)
                break;
            
            for(i=right;i>=left;i--)
                res[k++]=matrix[down][i];
            if(--down<up)
                break;
                
            for(i=down;i>=up;i--)
                res[k++]=matrix[i][left];
            if(++left>right)
                break;
        }
        return res;
    }
};

59. Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example, Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

这道题的思路和Spiral Matrix I如出一辙,只不过变成了给出大小,要求生成一个螺旋矩阵,我们依然声明up down left right四个变量,思路没什么差别,所以不再赘述。

代码如下:

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        if(!n)
            return {};
        vector<vector<int>> res(n,vector<int>(n, 0));/*初始化的时候要仔细考虑,第一次submission因为初始化导致了RTE*/
        int up=0,down=n-1,left=0,right=n-1,i=0,j=0,k=0,num=1;
        while(true){
            for(k=left;k<=right;k++){
                res[up][k]=num;
                num+=1;
            }
            if(++up>down)
                break;
            for(k=up;k<=down;k++){
                res[k][right]=num;
                num+=1;
            }
            if(--right<left)
                break;
            for(k=right;k>=left;k--){
                res[down][k]=num;
                num+=1;
            }
            if(--down<up)
                break;
            for(k=down;k>=up;k--){
                res[k][left]=num;
                num+=1;
            }
            if(++left>right)
                break;
        }
        return res;
    }
};