[每天刷 Leetcode-求组队] 54. 螺旋矩阵

2018-08-26 00:42:18 +08:00
 Acceml

题目

给定一个包含 m x n 个元素的矩阵( m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

题解

这个题目很简单,上下左右分别用四个变量去标志: 上:top 下:bottom 左:left 右: right

就按照四步走就可以:

  1. left -> right
  2. top -> bottom
  3. right -> left
  4. bottom -> top

每一步走完要对边界做出调整,具体看代码吧,清晰易懂。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        if (matrix.length == 0 || matrix[0].length == 0) return res;

        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;

        while (true) {
            for (int i = left; i <= right; i++) res.add(matrix[top][i]);
            top++;
            if (left > right || top > bottom) break;

            for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
            right--;
            if (left > right || top > bottom) break;

            for (int i = right; i >= left; i--) res.add(matrix[bottom][i]);
            bottom--;
            if (left > right || top > bottom) break;

            for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
            left++;
            if (left > right || top > bottom) break;
        }

        return res;
    }
}

热门阅读

4276 次点击
所在节点    C
32 条回复
CEBBCAT
2018-08-26 01:06:10 +08:00
是组队还是广告啊😯? @Livid 站长我都替你心疼你的鼠标微动
CEBBCAT
2018-08-26 01:14:04 +08:00
两个问题:
1. 为什么不换行?这样对后续阅读和维护有什么好处吗?比如:`if (left > right || top > bottom) break;`
2. res 数组为什么不事先划定大小?这样可以加快很多的吧
RqPS6rhmP3Nyn3Tm
2018-08-26 02:40:00 +08:00
这道题不难。用一个 rounds 记录转了几圈就可以了。
Acceml
2018-08-26 04:16:27 +08:00
@CEBBCAT 不是广告啊,就记录一下自己的公众号,没多少人关注,广告个毛线啊。
laxenade
2018-08-26 08:00:51 +08:00
剧透: 正确的做法是竖着 flip 一次然后横着 flip 一次
SorcererXW
2018-08-26 08:32:29 +08:00
如果用类似 dfs 搜索的方式思考的话, 可能会优雅一点(程序效率可能会低一点
初始向右方前进
如果当前方向可行, 就继续前进
如果不行了, 就切换到下一个方向
右的下一个方向是下, 下的下一个是左, 左的下一个是上, 上的下一个是右
k9ox
2018-08-26 08:40:24 +08:00
这题不难啊,讨论个屁啊😯我记得有一题是数独的解,难到爆炸,而且讨论区有李显龙的解法🤣🤣
msg7086
2018-08-26 09:11:29 +08:00
def spiral_order m
return [] if m.size == 0
m.shift + spiral_order(m.transpose.reverse)
end

之前看到过的写得最简洁的 Ruby 解法。
ayyll
2018-08-26 09:35:01 +08:00
打 cf 吧 半夜被 hack 到哭(逃
a554340466
2018-08-26 12:17:00 +08:00
这不就是 剑指 offer 前面章节讲的吗
LadyChunsKite
2018-08-26 19:20:47 +08:00
楼主该不会准备把这样的贴子发 800 多个吧?
Acceml
2018-08-26 22:02:12 +08:00
@laxenade 没懂,是啥意思。
Acceml
2018-08-26 22:02:57 +08:00
@LadyChunsKite 是的。
Acceml
2018-08-26 22:03:15 +08:00
@a554340466 嗯嗯,就是简单的找规律的题呗。
Acceml
2018-08-26 22:05:55 +08:00
@CEBBCAT 短小就是美。
Acceml
2018-08-26 22:06:21 +08:00
@k9ox 嗯嗯,不难,就是记录一下自己的题解。恰好有人讨论就更开心啦~~
Acceml
2018-08-26 22:11:01 +08:00
@msg7086 没写过 ruby,这个有顺序的 special order dfs 很屌的感觉,但是代码看起来不会很简洁?
Acceml
2018-08-26 22:17:40 +08:00
@ayyll 其实工作的技术能力并不等于 leetcode 算法能力,只是过段时间要准备跳槽,所以发在公众号上和大家交流一下。不然真他妈的坚持不下去啊。
zeR0f1re
2018-08-26 22:28:14 +08:00
@Acceml 抱抱粗腿,观摩一下
yumenawei
2018-08-26 23:22:15 +08:00
@Acceml 等十月份再看看?还是跳定了呀

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/483264

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX