leetcode_54

淳属虚构 · · 441 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Golang:

声明:这题我首先用了JAVA语言去实现,在通过所有测试用例后,发现结果如下:

测试结果

我觉得我实现的超烂,时间复杂度上(我预估)是超烂,空间复杂度上(从程序里就能看出来)也是超烂,结果这个程序的时间复杂度这么好?

思路:因为我今天是第一次做这道题,所以在所有算法里我可能会先写暴力一点的算法,即先做出来,再考虑优化。先上暴力求解的思路,即通过循环来实现,我们可以很明显的看出,螺旋式,其实就像剥洋葱一样,是一层一层地去剥的,我们可以拆解为,先输出最外圈,再输出内圈,当第一层外圈被输出后,第二层内圈即变成原来的外圈,于是就可以一直输出。

具体实现:我们可以考虑三种类型的二维数组,行数远大于列数的,列数远大于行数的,以及行数等于列数的。

那么问题有:

  • 一共要剥几层?
    在这里我认为,最多要剥min(m,n)/2+1层。这里大家可以简单用几个数组自己试一下即可。
  • 怎么剥?
    螺旋式的剥,数组先向右,再向下,再向左,最后向上。
  • 每一层剥到什么时候结束
    这个其实是关键问题,我采用的方法是,用另外一个同等大小的二维数组flag,每当我们访问了一次matrix[x][y]后,就将flag数组同等位置写成1,如果二维数组是n*n的,那么螺旋式输出,直至回到起始值为止。如果不是,我们去判断下flag[x][y]的值,如果它是1,那么说明该结束了。

Tips:如果你在一个循环里,定义变量x自增,希望x到达n时停止循环,那用x<n这一判断条件会好于x!=n

代码明天再补。。。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:淳属虚构

查看原文:leetcode_54

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

441 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传