V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  C

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

  •  
  •   Acceml · 2018-08-26 00:42:18 +08:00 · 4306 次点击
    这是一个创建于 2282 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给定一个包含 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;
        }
    }
    

    热门阅读

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

    之前看到过的写得最简洁的 Ruby 解法。
    ayyll
        9
    ayyll  
       2018-08-26 09:35:01 +08:00 via Android
    打 cf 吧 半夜被 hack 到哭(逃
    a554340466
        10
    a554340466  
       2018-08-26 12:17:00 +08:00 via iPhone
    这不就是 剑指 offer 前面章节讲的吗
    LadyChunsKite
        11
    LadyChunsKite  
       2018-08-26 19:20:47 +08:00   ❤️ 1
    楼主该不会准备把这样的贴子发 800 多个吧?
    Acceml
        12
    Acceml  
    OP
       2018-08-26 22:02:12 +08:00
    @laxenade 没懂,是啥意思。
    Acceml
        13
    Acceml  
    OP
       2018-08-26 22:02:57 +08:00
    @LadyChunsKite 是的。
    Acceml
        14
    Acceml  
    OP
       2018-08-26 22:03:15 +08:00
    @a554340466 嗯嗯,就是简单的找规律的题呗。
    Acceml
        15
    Acceml  
    OP
       2018-08-26 22:05:55 +08:00
    @CEBBCAT 短小就是美。
    Acceml
        16
    Acceml  
    OP
       2018-08-26 22:06:21 +08:00
    @k9ox 嗯嗯,不难,就是记录一下自己的题解。恰好有人讨论就更开心啦~~
    Acceml
        17
    Acceml  
    OP
       2018-08-26 22:11:01 +08:00
    @msg7086 没写过 ruby,这个有顺序的 special order dfs 很屌的感觉,但是代码看起来不会很简洁?
    Acceml
        18
    Acceml  
    OP
       2018-08-26 22:17:40 +08:00
    @ayyll 其实工作的技术能力并不等于 leetcode 算法能力,只是过段时间要准备跳槽,所以发在公众号上和大家交流一下。不然真他妈的坚持不下去啊。
    zeR0f1re
        19
    zeR0f1re  
       2018-08-26 22:28:14 +08:00
    @Acceml 抱抱粗腿,观摩一下
    yumenawei
        20
    yumenawei  
       2018-08-26 23:22:15 +08:00
    @Acceml 等十月份再看看?还是跳定了呀
    snxq1995
        21
    snxq1995  
       2018-08-26 23:28:43 +08:00   ❤️ 1
    开个群比较好交流,这样的公众号其他人参与度不高。
    ayyll
        22
    ayyll  
       2018-08-27 07:53:58 +08:00 via Android
    @Acceml leetcode 太水了 真谈算法能力 还是上 tc/cf 吧 打到 rank 前 10 标准的青年计算机科学家
    Acceml
        23
    Acceml  
    OP
       2018-08-27 09:47:36 +08:00
    @snxq1995 好滴~~
    Acceml
        24
    Acceml  
    OP
       2018-08-27 09:48:22 +08:00
    @yumenawei 看看再跳呗。
    Acceml
        25
    Acceml  
    OP
       2018-08-27 09:52:44 +08:00
    @ayyll 我的初衷就是为了准备下面试,我认为算法能力和工程能力完全不等价。不会花很多时间在上面,你所谓的水在我看来足够即可。
    Elephant696
        26
    Elephant696  
       2018-08-27 09:58:19 +08:00
    这个题,,,以前面试的时候二面面试官叫我用笔手写这个算法,,,我当时告诉他说我只能说思路,手写写不出来,然后被对方请出去了,没错,是请出去了。记忆深刻。
    PS:我面试是前端。。。
    coffeSlider
        27
    coffeSlider  
       2018-08-27 11:36:32 +08:00 via Android
    这个题只用一个变量就能解呢
    Acceml
        28
    Acceml  
    OP
       2018-08-27 13:26:11 +08:00
    @Elephant696 哪家面试官,这么虎的吗?
    Acceml
        29
    Acceml  
    OP
       2018-08-27 13:26:33 +08:00
    @coffeSlider 用一个变量,需要记住走的步数?
    coffeSlider
        30
    coffeSlider  
       2018-08-27 13:55:51 +08:00 via Android
    @Acceml 简单的来说,就是用一个数来记录四个方向和走了几圈
    ayyll
        31
    ayyll  
       2018-08-27 15:40:43 +08:00 via Android
    @Acceml 行 8 good luck
    Elephant696
        32
    Elephant696  
       2018-08-28 16:20:18 +08:00 via iPhone
    @Acceml 一个创业公司,名字就不说了。太菜了不敢大声说话
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2668 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 05:31 · PVG 13:31 · LAX 21:31 · JFK 00:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.