V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
chenggiant
V2EX  ›  问与答

面试时的一道算法题,大家来挑战下吧

  •  
  •   chenggiant · 2014-03-05 14:04:34 +08:00 · 4250 次点击
    这是一个创建于 3901 天前的主题,其中的信息可能已经有所发展或是发生改变。
    给定一个文件,里面有10000个数字,数字只从{1,2,3,4}里面选取。这些数字排成100*100的网格。找出里面序列 1234 以顺时针出现的次数(闭环)。

    例子:
    3 3 1 2
    1 2 3 4
    4 3 2 3
    1 1 1 4

    比如这个例子里面,1234 以顺时针出现了两次。

    我能想到的只能是遍历了...大家有什么好的思路么?
    第 1 条附言  ·  2014-03-06 00:00:34 +08:00
    谢谢大家的回复呀。

    决定看下Rabin–Karp algorithm,感觉可以用在这种情况。
    22 条回复    1970-01-01 08:00:00 +08:00
    cxe2v
        1
    cxe2v  
       2014-03-05 14:12:42 +08:00
    不在一行的顺时针也算么?
    cxe2v
        2
    cxe2v  
       2014-03-05 14:13:27 +08:00
    @cxe2v 额,刚理解错了
    nigelvon
        3
    nigelvon  
       2014-03-05 14:16:52 +08:00
    遍历复杂度应该也不高哇。
    ETiV
        4
    ETiV  
       2014-03-05 14:17:56 +08:00
    * * * *
    1 2 * *
    3 4 * *
    * * * *

    我肉眼只看到了这一个呀, 那个呢?
    alsotang
        5
    alsotang  
       2014-03-05 14:19:28 +08:00
    遍历的复杂度是 O(n)的吧,还能少?
    lsylsy2
        6
    lsylsy2  
       2014-03-05 14:19:41 +08:00
    100*100……遍历也很快吧?
    bleutee
        7
    bleutee  
       2014-03-05 14:21:06 +08:00
    @ETiV
    * * * *
    * * * *
    * * 2 3
    * * 1 4
    chenggiant
        8
    chenggiant  
    OP
       2014-03-05 14:21:13 +08:00
    @ETiV

    1 2
    4 3

    2 3
    1 4

    额,我可能还是没说清楚呀。
    a591826944
        9
    a591826944  
       2014-03-05 14:22:03 +08:00   ❤️ 1
    从 行里面 遍历相邻的两个数字 相加 等于 3/5/7 如果是 记位置,看下一行这个位置的两个数字 是不是能组成符合规则的,如果不是 下一行的这个位置 就不用看了 肯定不行
    这样就不用便利全部的矩阵了
    justfindu
        10
    justfindu  
       2014-03-05 14:26:12 +08:00
    @a591826944 这样下一行的这个位置也有可能是下下行的符合要求的~ 还是要遍历的啊
    forestkeeper
        11
    forestkeeper  
       2014-03-05 14:59:54 +08:00   ❤️ 1
    @alsotang 能的,和kmp算法差不多的方案来剪枝,可以跳着遍历
    binux
        12
    binux  
       2014-03-05 15:30:49 +08:00   ❤️ 1
    顺时针,还要闭环,总共就4种可能,这太简单了吧。。
    读一行,缓存下一行,如果第一行相邻两个数字满足,判断下一行是否一样满足。O(n)而已

    要不我们来改一下,只要4个数字相连(4/8个方向),能组成1234即可,有多少种。
    marklrh
        13
    marklrh  
       2014-03-05 16:01:59 +08:00
    @a591826944 只看相加的值可以么?有可能是逆时针的啊
    shibo501c
        14
    shibo501c  
       2014-03-05 17:50:14 +08:00
    感觉可以预处理一下,数组存起来,可以计算四个相邻位置的和,如果是10,就存起来,然后再统一看下是不是顺序的,这样会优化一些吧
    Sdhjt
        15
    Sdhjt  
       2014-03-05 17:56:47 +08:00
    还是遍历吧,反正复杂度不高
    hongdengdao
        16
    hongdengdao  
       2014-03-05 21:29:35 +08:00
    开始只要找通过找到1的上边或者右边为2的位置,在这些为2的位置对应的顺时针位置。。。直到找到4
    hongdengdao
        17
    hongdengdao  
       2014-03-05 21:31:32 +08:00   ❤️ 1
    总之只要先找1即可
    acros
        18
    acros  
       2014-03-05 21:40:16 +08:00
    最好的情况一时想不到,因为这个要求2x2的,肯定能跳着好些···
    laoyang945
        19
    laoyang945  
       2014-03-06 11:45:51 +08:00
    我遇到一个相同的题目,不过是在10000*10000的矩阵里面找一个3*3 的模式出现的次数,该模式正中央那格无需匹配
    chenggiant
        20
    chenggiant  
    OP
       2014-03-06 13:07:18 +08:00
    @laoyang945 感觉你这个更复杂啊。有想到好的方法么?
    RobinFai
        21
    RobinFai  
       2014-03-06 15:02:16 +08:00
    码渣只能写成这样了.......

    https://gist.github.com/robinfai/9383871
    momou
        22
    momou  
       2014-03-06 18:55:08 +08:00
    刚学JS,试着做了下
    https://gist.github.com/9387095
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1374 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 17:39 · PVG 01:39 · LAX 09:39 · JFK 12:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.